Find the congruence of $4^{578} \pmod 7$

Find the congruence of $4^{578} \pmod 7$.

Can anyone calculate the congruence without using computer?

Thank you!

-
Thank you. @MartinSleziak –  J.A.F Oct 21 '12 at 7:50
Note that $4^3=64\equiv 1\pmod 7$. –  Hagen von Eitzen Oct 21 '12 at 7:50

Use the fact that $$4^{3} \equiv 1 \ (\text{mod 7})$$ along with if $a \equiv b \ (\text{mod} \: m)$ then $a^{n} \equiv b^{n} \ (\text{mod}\: n)$.

-

Using Fermat's Little theorem:

If p is a prime and a is an integer, then $a^{p-1}\equiv1$ (mod p), if p does not divide a.

$4^{6}\equiv1 (mod 7)$

Since $4^{578}=(4^{6})^{96}\cdot4^{2}$, we can conclude that$4^{578}\equiv1^{96}\cdot4^{2}(mod 7)$.

Hence$4^{578}\equiv2(mod 7)$.

-
Could any one review it? –  J.A.F Nov 7 '12 at 14:57