4
$\begingroup$

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$?
  • 1
    Yes.${}{}{}{}{}$2012-09-19
  • 0
    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*.2012-09-19
  • 0
    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$2012-09-19
  • 0
    @CodeKingPlusPlus, ah ok.2012-09-19

1 Answers 1