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
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$.
No comments:
Post a Comment