hi
I would be grateful if someone could walk me through how exactly to calculate $\displaystyle 3^{40}\, (mod 7) $
I know that I can take $\displaystyle 3^{40}\, (mod 7) \equiv (3\, (mod 7))^{40}$
How do I proceed?
Since 7 is prime we can use fermat little theorem
ie
$\displaystyle a^{p-1} \equiv 1 \mod (p)$
so we get
$\displaystyle 3^6 \equiv 1 \mod (7)$
now $\displaystyle 6|40$ to give $\displaystyle 40=6\cdot 6+4$
so now $\displaystyle 3^{40}=(3^6)^6\cdot 3^4 $
But now mod 7 we know that this is the same as
$\displaystyle (3^6)^6\cdot 3^4 \mod (7) =1^6\cdot 3^4 \mod (7)$
$\displaystyle 81 \mod (7)=4\mod (7)$
So basically, if I take another example, quite similar:
$\displaystyle 4^{15}\, (mod\, 7) $
Fermats little theorem gives us:
$\displaystyle 4^{6} \equiv 1 \, (mod \, 7) $ , and
$\displaystyle 4^{15}=(4^{6})^{2} \cdot 4^{3} $ $\displaystyle \Rightarrow 4^{15} \, (mod\, 7) \equiv (4^{6})^{2} \cdot 4^{3} \, (mod\, 7 ) \equiv 4^{3} \, (mod\, 7) \equiv 64 \, (mod\, 7)\equiv 1 \, (mod\, 7 ) $ ?