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

Question

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

Can anyone calculate the congruence without using computer?

Thank you!

Answer 1

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

Answer 2

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