A discrepancy in the proof that 561 is Carmichael number.

Question

The proof is given below:

But I do not understand the statement in the line before last which says "These give rise to the single congruence $a ^{560} \equiv 1 \pmod n$ where gcd(a, 561) = 1 ", I do not know why the previous mentioned system of linear congruences leads to this single congruence, what theorem is used to say this? is it the Chinese Remainder theorem ? if so how?

Answer 1

Since $a^{560}$ is congruent to $1$ modulo $3,11,$ and $17$, you know that $a^{560}-1$ is divisible by $3,11,$ and $17$. Thus, since $3,11,$ and $17$ are mutually coprime, $a^{560}-1$ is divisible by $3\cdot 11\cdot 17=561$ and so $a^{560}$ is congruent to $1$ modulo $561$.

Answer 2

The previous equations say that the integers $3,11$ and $17$ all divide $a^{560}-1$. This implies that their lcm must divide $a^{560}-1$ as well. But since $3,11,17$ are relatively prime their lcm is just their product which is $561$. So $561$ divides $a^{560}-1$, which means $a^{560}\equiv 1$(mod $561$).

Answer 3

It is indeed the chinese remainder theorem:

Chinese remainder Theorem

If a system of equations

$x \equiv a_i \mod m_i$ for some $i=1,2,\ldots,n$, with pairwise coprime $m_i$, then there is a unique solution mod $m_1m_2\cdots m_n$

Applying this to $m_1=3,m_2=11,m_3=17$ and $a_1=a_2=a_3=1$ gives the desired result.

Answer 4

You can see this as a consequence of the Chinese Remainder Theorem. Setting $x=a^{560}$, you have a system that says $$\begin{align*} x&\equiv 1\pmod{3}\\ x&\equiv 1\pmod{11}\\ x&\equiv 1\pmod{17} \end{align*}$$ By the Chinese Remainder Theorem, there is a unique solution modulo $3\times 11\times 17$, that is, $x\equiv b\pmod{561}$. But clearly, $b=1$ is a solution, so that is the unique solution. Hence $a^{560}=x\equiv 1\pmod{561}$.