0
$\begingroup$

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

Can anyone calculate the congruence without using computer?

Thank you!

  • 4
    Note that $4^3=64\equiv 1\pmod 7$.2012-10-21

2 Answers 2

1

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

  • 0
    Could any one review it?2012-11-07
6

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}\: m)$.