1. ## Congruence

hi

I would be grateful if someone could walk me through how exactly to calculate $3^{40}\, (mod 7)$

I know that I can take $3^{40}\, (mod 7) \equiv (3\, (mod 7))^{40}$

How do I proceed?

2. Originally Posted by Twig
hi

I would be grateful if someone could walk me through how exactly to calculate $3^{40}\, (mod 7)$

I know that I can take $3^{40}\, (mod 7) \equiv (3\, (mod 7))^{40}$

How do I proceed?
Since 7 is prime we can use fermat little theorem

ie

$a^{p-1} \equiv 1 \mod (p)$

so we get

$3^6 \equiv 1 \mod (7)$

now $6|40$ to give $40=6\cdot 6+4$

so now $3^{40}=(3^6)^6\cdot 3^4$

But now mod 7 we know that this is the same as

$(3^6)^6\cdot 3^4 \mod (7) =1^6\cdot 3^4 \mod (7)$

$81 \mod (7)=4\mod (7)$

3. So basically, if I take another example, quite similar:

$4^{15}\, (mod\, 7)$

Fermats little theorem gives us:

$4^{6} \equiv 1 \, (mod \, 7)$ , and

$4^{15}=(4^{6})^{2} \cdot 4^{3}$ $\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 )$ ?

4. Originally Posted by Twig
So basically, if I take another example, quite similar:

$4^{15}\, (mod\, 7)$

Fermats little theorem gives us:

$4^{6} \equiv 1 \, (mod \, 7)$ , and

$4^{15}=(4^{6})^{2} \cdot 4^{3}$ $\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 )$ ?
Yes you got it

5. Thanks again!