3
$\begingroup$

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 Answers 1

5

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?

  • 0
    @AgentKC Exactly, glad to help.2011-11-17