Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Can anyone calculate the congruence without using computer?

Thank you!

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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
Could any one review it? –  J.A.F Nov 7 '12 at 14:57

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.