1. ## Congruence

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?

2. Originally Posted by Twig
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)$

3. 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 )$ ?

4. Originally Posted by Twig
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 )$ ?
Yes you got it

5. Thanks again!