Why does $561$ divides $3^{561}-3$ if it doesn't divide $3$ nor $3^{560} -1$

Question

$561$ is a Carmicheal number. I was asked in an exercise to prove that it is so by proving that $561 | a^{561}-a$ for any integer a.

Now, if $561 | 3^{561}-3$ then $561|3*(3^{560}-1)$

But since $\gcd(561,3) > 1$ then it is false that $561 | 3^{560}-1$ (Isn't it?)

Then $561 | 3$ which is false.

Then by counterexample it would be false that $561 | a^{561}-a$ for any integer a.

What I am missing in the argument?

Thanks.

Answer 1

You have $561 = 3 \cdot 187$, so $561$ divides $3x$ iff $187$ divides $x$. You don't need another factor of 3.

Answer 2

Try your argument with different numbers

If $6 \mid 12$, then $6 \mid 3 \cdot 4$

But since $\gcd(6,3) > 1$ then it is false that $6 \mid 4$ (Isn't it?)

Then $6 \mid 3$ which is false.

Answer 3

Divide by $3$ to get $$561|3(3^{560}-1)\iff 187|(3^{560}-1)$$

Answer 4

To answer the title question, note that Euclid’s lemma that $p|ab\implies p|a$ or $p|b$ works for prime numbers $p$, but $561$ isn’t prime.

(In fact, in abstract algebra, $p$ is prime is defined as $p|ab\implies p|a$ or $p|b$ .)