Questions tagged [modular-arithmetic]

Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $a-b$.

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
1
vote
0 answers

Integers and Division, Modular Arithmetic...

Hi is there anything wrong with the following? Q1: Express gcd(2,17) as a linear combination of 2 and 17 gcd(2,17) 17 = 8 * 2 + 1 2 = 2 * 1 gcd(2,17) = 1 1 = -8 * 2 + 17 ∴ gcd(2,17) = 1 = (-8) 2 + (1) 17 Q2: Find an inverse of 2 modulo 17 2(mod…
1
vote
4 answers

Find 7th root of 23 modulo 143

I am trying to find $x$ such that $x\equiv23^{\frac{1}{7}}\mod 143$, but am not really sure where to start. I would expect that, in order to solve this, I would have to rewrite my formula to something as follows: $$ x\equiv 23^{\frac{1}{7}}\mod 143…
56LzXNcyp
  • 113
1
vote
1 answer

Modular arithmetic with floor function

The following attached image is the problem I need help on. Thank you so much. Prove that $a\mod m=a-\left[\frac am\right]m$ where $$[x]=\max\left\{y\in \Bbb Z, y\leq x\right\}$$
1
vote
1 answer

Prove that the only integer solution to the equation $x^2+y^2=3z^2$ is $x=y=z=0$.

I started by saying that $x^2$ and $y^2$ must be divisible by 9 because they are perfect squares and must add to a multiple of three. $z^2$ also must be a multiple of 9, otherwise the equation wouldn't be correct. $3z^2$ will have an extra multiple…
Gerard L.
  • 2,536
1
vote
1 answer

Modular Arithmetic Question $p(x)=x^2-x+41$

Can someone give me a hint on this problem please? Show that the polynomial $p(x)=x^2-x+41$ takes prime values for x in the set (0,1,2,...,40) Thanks in advance!
1
vote
1 answer

Euler Fermat Theorem with composites

Show that for every integer $a$ such that $\gcd(a,100)=1$, $a^{100}= 1 \mod 100$ and use this to compute the last two digits of $(11)^{102}$. Can you say something more precise about the order of an element in $(\mathbf{Z}/100 \mathbf{Z} )^*$? So,…
GGG
  • 11
1
vote
3 answers

Solve $\begin{cases}8x^{329} + 6x^{628} -2 \equiv 1 \pmod {15}\\(x^{1328} - 4)^2 \equiv 0 \pmod 7\end{cases}$ .

I came across this problem and have absolutely no idea how to solve it. The system is as follows $$\begin{cases}8x^{329} + 6x^{628} -2 \equiv 1 \pmod {15}\\(x^{1328} - 4)^2 \equiv 0 \pmod 7\end{cases}$$ I appreciate any help you can give me
1
vote
3 answers

Not understanding modulo

I'm not sure if I'm in the right place, but I'll give it a try! I'm very bad with mathematics even though it's pretty interesting. Well, for Java programming we have to use the modulo operator, but I just don't get the modulo it self. I hope any of…
1
vote
2 answers

Quadratic equations using modular arithmetic

I have a problem I want to solve, but I could not figure out how to approach it. And since I do not have formal maths training, I am not very familiar with the terminology so it is possible I may not know the correct keywords for search. Below are a…
xycf7
  • 131
1
vote
1 answer

Modulo $x^y \pmod n$ correctly??

I have an RSA example to solve. I got my decryption key and now I need to calculate the modulo $d^e \pmod n$. Here is the example $$ 1007^{10} \mod 3599. $$ What I am trying is $$ 1007^3 \times 3 = 3063442029 + 1007^1 = 3063443036. $$ Then I am…
1
vote
1 answer

Fast algorithm to get $k^n \pmod{ka}$

The title is a question itself. Does exist any fast algorithm to get $$k^n \pmod{ka}$$ ? ($k, a, n > 1 $, natural number)
plhn
  • 631
1
vote
3 answers

Formula for consecutive residue of primitive modulo n.

\begin{align*} 3^0 \equiv 1\mod 7\\ 3^1 \equiv 3\mod 7\\ 3^2 \equiv 2\mod 7\\ 3^3 \equiv 6\mod 7\\ 3^4 \equiv 4\mod 7\\ 3^5 \equiv 5\mod 7\\ 3^6 \equiv 1\mod 7\\ 3^7 \equiv 3\mod 7\\ \end{align*} Now just focusing on 1, 3, 2, 6, 4, 5, 1.... How to…
1
vote
2 answers

Fastest way to compute [1234567890]_200 with pen and paper

I'm wondering if there is a more elegant and faster way to compute $1234567890 \bmod 200$ with pen and paper than doing the arithmetic division. Thanks
1
vote
1 answer

Proof help needed about order of a number & congruences

$\def\ord{\operatorname{ord}}$I could not prove the following statement. Could you please help me? Let $\ord_p a = p-1$. Show that for every $c∈\mathbb Z$, $\gcd(c,p)=1$, there exists $1≤i≤p-1$ such that $c≡a^i \pmod p$
Xentius
  • 1,151
1
vote
0 answers

Modulo inverse via quadratic resiude?

I've found this snippet in the guts of GCC compiler. This is modulo inverse. /* Computes inverse to X modulo (1 << MOD). */ static uint64_t inverse (uint64_t x, int mod) { uint64_t mask = ((uint64_t) 1 << (mod - 1) << 1) - 1; uint64_t…