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.

I need help getting started on a longer proof and this is the first part:

Show that if $\gcd(a, 3) = 1$, then $a^{560} = 1 \pmod 3$

Then we show the same thing with $11, 17, 561$. I have a feeling the same technique will be used to prove all of them, so if it can, all I really need to know is how to prove the first part.

The eventual goal is that we've shown $561$ is composite, but will pass the Fermat Primality Test.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Since $a$ and $3$ are coprime, Fermat's little theorem says $a^2\equiv 1\pmod{3}$. Can you use that to show what you want?

share|improve this answer
    
So, does this mean I can remove all the powers of 2 (since they are congruent to 1 (mod 3)) and be left with $a^{35} mod (3)$? Or is that the wrong direct to go? –  TheEnigmaMachine Nov 17 '11 at 3:14
    
@AgentKC, It means you can remove all even powers of $a$. But notice $a^{560}\equiv (a^2)^{280}\equiv 1^{280}\equiv 1\pmod{3}$. –  yunone Nov 17 '11 at 3:16
    
Ohhh! That makes a lot more sense! And then we can do basically the same thing for the other numbers. Thank you! –  TheEnigmaMachine Nov 17 '11 at 3:17
    
@AgentKC Exactly, glad to help. –  yunone Nov 17 '11 at 3:18

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.