Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Can anyone calculate the congruence without using computer?

Thank you!

share|cite|improve this question
    
    
Thank you. @MartinSleziak – John Hass 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

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

share|cite|improve this answer
up vote 1 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|cite|improve this answer
    
Could any one review it? – John Hass Nov 7 '12 at 14:57

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.