[Math] gcd and fermat’s little theorem

elementary-number-theorymodular arithmetic

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$?

Best Answer

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$)

Related Question