# How can I show that if $\gcd(a, 3) = 1$, then $a^{560} = 1 \pmod 3$?

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.

-

## 1 Answer

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?

-
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