Needing help finding the least nonnegative residue

Question

1. $2^{47} \bmod 23$
2. $776^{79} \bmod 7$
3. $12347369^{3458} \bmod 19$
4. $5^{18} \bmod 13$
5. $23^{560} \bmod 561$

I really don't understand how to calculate the ones to powers. Could anyone explain how to do one of these examples?

Answer 1

First make sure that you reduce the element which you want to exponentiate. After this you should apply Euler's theorem to reduce the exponent (note that this is only possible if the element you want to exponentiate is relatively prime to the modulus.

I will do $776^{79}$ as an example:

$776^{79}\equiv 6^{79}\bmod 7$ since $776\equiv 6 \bmod 7$

$6$ and $7$ are relatively prime so we can use euler's theorem, it tells us $6^{\varphi(7)}\equiv 1 \bmod 7$. Since $7$ is prime $\varphi(7)=7-1=6$ so we have $6^{6}\equiv 1 \bmod 7$. We can now finish:

$6^{79}=6^{78}\cdot 6=(6^6)^{13}\cdot 6\equiv 1\cdot 6\equiv 6\bmod 7$

Therefore $776^{79}\equiv 6 \bmod 7$.

Answer 2

Euler's theorem ($(a,n)=1\,\Rightarrow\,a^{\phi(n)}\equiv 1\pmod{\!n}$) implies Fermat's little theorem (FLT): $p\nmid a\,\Rightarrow\, a^{p-1}\equiv 1\pmod{\! p}$, since $\phi(p)=p-1$ ($p$ is prime).

$\bmod 23\!:\ 2^{47}\stackrel{\text{FLT}}\equiv 2^{47\!\pmod{\! 22}}\!\equiv 2^3\equiv 8$.

$\bmod 7\!:\ 776^{79}\equiv (-1)^{79}\equiv -1\equiv 6$.

$\bmod 19\!:\ 12347369^{3458}\equiv 10^{3458}\stackrel{\text{FLT}}\equiv 10^{3458\!\pmod{\! 18}}\!\equiv 10^2\equiv 5$.

$\bmod 13\!:\ 5^{18}\equiv 25^9\equiv (-1)^9\equiv -1.$

$561=3\cdot 11\cdot 17$.

$\bmod 3\!:\ 23^{560}\equiv (-1)^{560}\equiv 1$.$\:$ $\bmod 11\!:\ 23^{560}\equiv 1^{560}\equiv 1$.

$\bmod 17\!:\ 23^{560}\stackrel{\text{FLT}}\equiv 23^{560\!\pmod{\! 16}}\!\equiv 23^0\equiv 1$.

$3,11,17\mid 23^{560}-1\,\Rightarrow\, 561\mid 23^{560}-1$, since $\text{lcm}(3,11,17)=561$.

We got lucky that $23^{560}\!\bmod{7}=23^{560}\!\bmod{11}=23^{560}\!\bmod{17}$. This is often not the case
($\!\bmod{}\!$ here (unlike above) is an operation that gives the least residue, as opposed to an equivalence relation, in which integers with the same residues are equivalent, denoted $\equiv$).

In general, finding residues mod composite $n$ can be done using the following algorithm. CRT (Chinese remainder theorem) says that given residues mod coprime $a_i$, there is a unique residue mod $a_1a_2\cdots a_k$ (and trivially a residue mod $a_1a_2\cdots a_k$ gives unique residues to coprime $a_i$).

E.g., find $18^{55}\!\bmod{170}$. $\: 170=2\cdot 5\cdot 17$.

$\bmod 2\!:\ 18^{55}\equiv 0\,\Rightarrow\, 18^{55}=2k$.

$\bmod 5\!:\ 18^{55}\equiv 3^{55}\stackrel{\text{FLT}}\equiv 3^{55\!\pmod{\! 4}}\!\equiv 3^3\equiv 2\equiv 2k\,\Leftrightarrow k\equiv 1\,\Rightarrow\, k=5l+1$.

$\bmod 17\!:\ 18^{55}\equiv 1^{55}\equiv 1\equiv 2(5l+1)\equiv 10l+2\,\Leftrightarrow\, 10l\equiv -1\equiv 50\,\stackrel{:10}\Leftrightarrow\, l\equiv 5$.

$18^{55}=2(5(17m+5)+1)=2(85m+26)=170m+52$.