Modulo: Calculating without calculator??

Question

Calculate the modulo operations given below (without the usage of a calculator):

$101 \times 98 \mod 17 =$

$7^5 \mod 15 =$

$12^8 \mod 7 =$

$3524 \mod 63 =$

$−3524 \mod 63 =$

Ok with calculator I have no problem with it. However, I need to learn how can I compute them without calculator.

Answer 1

By definition of modular arithmetic, $3524 \pmod{63}$ is the remainder when $3524$ is divided by $63$.

To find $-3524 \pmod{63}$, multiply your answer for $3524 \pmod{63}$ by $-1$. If you want a positive residue, add $63$ to this result.

For the product $101 \cdot 98 \mod{17}$, use the theorem that if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$.

Since $101 = 5 \cdot 17 + 1$, $101 \equiv 16 \pmod{17}$. Since $98 = 5 \cdot 17 + 13$, $98 \equiv 13 \pmod{17}$. Thus,

$$101 \cdot 98 \equiv 16 \cdot 13 \equiv 208 \equiv 4 \pmod{17}$$

since $208 = 12 \cdot 17 + 4$.

However, you can simplify the calculations further if you use residues with absolute value at most $n/2$.

Since $101 = 6 \cdot 17 - 1$, $101 \equiv -1 \pmod{17}$. Since $98 = 6 \cdot 17 - 4$, $98 \equiv -4 \pmod{17}$. Thus,

$$101 \cdot 98 \equiv -1 \cdot -4 \equiv 4 \pmod{17}$$

which agrees with our previous result.

For $12^8 \pmod{7}$, observe that $12 \equiv 5 \pmod{7}$, so $12^8 \equiv 5^8 \pmod{7}$.

If $p$ is a prime modulus and $k \neq 0$, then $k^{p - 1} \equiv 1 \pmod{p}$. Hence, $5^6 \equiv 1 \pmod{7}$, so

$$12^8 \equiv 5^8 \equiv 5^65^2 \equiv 5^2 \equiv 4 \pmod{7}$$

For $7^5 \pmod{15}$, reduce modulo $15$ after you calculate each power. For instance,

$$7^2 \equiv 49 \equiv 4 \pmod{15}$$

so

$$7^3 \equiv 7 \cdot 7^2 \equiv 7 \cdot 4 \equiv 28 \equiv -2 \pmod{15}$$

Since you know the residues of $7^2 \pmod{15}$ and $7^3 \pmod{15}$, you can multiply their residues to find the residue of $7^5 = 7^2 \cdot 7^3$ modulo $15$. If you want a positive residue, add a suitable multiple of $15$.

Answer 2

Hint for the first one: $$101 \times 98 \mod 17 = (101 \mod 17) \times (98 \mod 17)$$ $$ = (16 \times 13) \mod 17$$

Similarly, for the third one, it can be simplified by turning $$12^8 \mod 7 =$$

The base has a residue of 5, and only multiplies with itself, so we only need the residue. As for the power, because its mod 7, we know that the answer has 6 possibilities (because its prime, it can be 0). It will cycle through these, in at most 6 steps, so we can remove the seven to simplify it. So, we subtract 6 from 8, and get $$=5^2 \mod 7$$ $$=25 \mod 7$$

Answer 3

Start by learning Fermat's little theorem, then move to the generalized version with Euler's totient function. After that, learn the Chinese remainder theorem.