Modulo: Calculating Without Calculator? ?

Modulo: Calculating Without Calculator? ?
$\begingroup$

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.

$\endgroup$
2

3 Answers

$\begingroup$

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$.

$\endgroup$
$\begingroup$

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$$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Alexander Ross
Author

Alexander Ross

Alexander Ross has covered the video game industry for a decade, writing deep dives on game design, esports tournaments, VR developments, and gaming culture.