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:
- gcd($b$, $3$) = $1$ so I can then apply Fermat's Little Theorem: $b^2$ $\equiv$ $1$ mod $3$
- 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$)