# gcd and fermat's little theorem

I know the following: gcd($b$, $561$) = $1$ How can I show that $b^{560}$ $\equiv$ $1$ mod $3$ ? I see that $561$ is not prime as $561$ = $3*11*17$. My first thoughts are:

1. gcd($b$, $3$) = $1$ so I can then apply Fermat's Little Theorem: $b^2$ $\equiv$ $1$ mod $3$
2. Can I simply exponentiate both sides of the congruence by the power $280$?
• Yes.${}{}{}{}{}$ – Gerry Myerson Sep 19 '12 at 0:03
• Are you sure you have this right? Perhaps the congruence is mod 561, not 3. 561 is a special number that satisfies Fermat's theorem without being a prime; 561 is a Carmichael number. – lhf Sep 19 '12 at 0:05
• Yes, the idea is once I can build $b^{560}$ $\equiv$ $1$ mod $3$, I can do the same thing with $11$ and $17$ and since $3*11*17$ = $561$ I can appeal to the Chinese remainder theorem and then conclude that $b^{560}$ $\equiv$ $1$ mod $561$ – CodeKingPlusPlus Sep 19 '12 at 0:11
• @CodeKingPlusPlus, ah ok. – lhf Sep 19 '12 at 0:31

Since gcd$(b, 3) = 1$, $b^2 \equiv 1$ (mod $3$) by the Fermat's little theorem. Since $b^{560} = (b^2)^{280}$, $b^{560} \equiv 1$ (mod $3$)