..
$\displaystyle 5^6 = (5^3)^2 = 125^2$
And
$\displaystyle 125 \equiv 52~\text{mod 73}$
So
$\displaystyle 5^6 = 125^2 \equiv 52^2~\text{mod 73}$
Now
$\displaystyle 52 = 4 \cdot 13 = 2^2 \cdot 13$
Thus
$\displaystyle 5^6 \equiv 52^2 = (2^2 \cdot 13) = 2^4 \cdot 13^2$
So finally:
$\displaystyle \equiv 16 \cdot 169 = 16 \cdot 23 = 8 \cdot 46 = 4 \cdot 92 \equiv 4 \cdot 19 = 76 \equiv 3~\text{mod 73}$
-Dan
Hello, yellow4321!
You have a calculator that can perform division with remainder 73
but cannot store nor output any number of size greater than $\displaystyle \pm200$
Show how to calculate: .$\displaystyle 5^6 \pmod{73}$
Calculate successive powers of 5, reducing modulo 73.
$\displaystyle 5^1 \;\equiv \;5 \pmod{73}$
$\displaystyle 5^2\;\equiv\; 25 \pmod{73}$
$\displaystyle 5^3 \;\equiv\;125 \;\equiv\;\text{-}21 \pmod{73}$
$\displaystyle 5^4\;\equiv\;\text{-}105 \;\equiv\;\text{-}32 \pmod{73}$
$\displaystyle 5^5 \;\equiv\;\text{-}160 \;\equiv\;\text{-}14 \pmod{73}$
$\displaystyle 5^6 \;\equiv\;\text{-}70 \;\equiv\;3 \pmod{73}$
By Fermat's Little Theorem,
$\displaystyle 5^{72} \equiv 1 \pmod{73}$
But
$\displaystyle \underbrace{(5^6)(5^6)(5^6)...}_{12\ times}\equiv \underbrace{(3)(3)(3)...}_{12 \ times} \pmod{73}$
$\displaystyle \Rightarrow 5^{72} \equiv 36 \pmod{73}$
Is this correct? Why or why not?