# Fermat's little theorem and solving system of congruences

The question:

The number $561$ factors as $3 \cdot 11 \cdot 17$. First use Fermat's little theorem to prove that $$a^{561} \equiv a \pmod 3 \\ a^{561} \equiv a\pmod {11} \\ a^{561} \equiv a\pmod {17}$$ for every value of $a$. Then explain why these three congruences imply that $a^{561} \equiv a (\mod 561)$ for every value of $a$.

My attempt: $$a^2 = \left\{ \begin{array}{c} 1 (\mod 3) \quad \text{if} \quad 3 \mid a\\ 0 (\mod 3) \quad \text{if} \quad 3 \nmid a\\ \end{array} \right. \\[3ex] a^{10} = \left\{ \begin{array}{c} 1 (\mod 11) \quad \text{if} \quad 11 \mid a\\ 0 (\mod 11) \quad \text{if} \quad 11 \nmid a\\ \end{array} \right. \\[3ex] a^{16} = \left\{ \begin{array}{c} 1 (\mod 17) \quad \text{if} \quad 17 \mid a\\ 0 (\mod 17) \quad \text{if} \quad 17 \nmid a\\ \end{array} \right.$$ I'm really not sure where to go from here. The fact that $561 = 3\cdot 11 \cdot 17$ must fit in somehow, but beyond that I don't know.

• Hint: Use the Chinese remainder theorem. B.t.w., what does ‘proving a system of congruences’ mean? – Bernard Jul 27 '17 at 16:35
• Nothing, apparently. I guess since it involved three systems, and proofs, that that title made sense. – John Jul 27 '17 at 16:36
• You solve a system of congruences, you do not prove it. It is not an assertion. Or you prove it has a solution. – Bernard Jul 27 '17 at 16:39

Presumably you can see that $$a^{k} \equiv \left\{ \begin{array}{c} 1 \bmod p \quad \text{ if } p \nmid a\\ 0 \bmod p \quad \text{ if } p \mid a\\ \end{array} \right.$$

immediately gives $a^{k+1} \equiv a \bmod p$ and indeed $a^{nk+1} \equiv a \bmod p$

The key next step is to examine the factors of $561-1=560$.

$560 = 2^4\cdot5\cdot7$

And in particular, note
\begin{align} 2 &\mid 560 \\ 10 &\mid 560 \\ 16 &\mid 560\end{align}

Once you have demonstrated the three asserted equivalences to the individual primes, the result for the composite value follows immediately from "simple" equal values in the Chinese Remainder Theorem: given $b,c,$ coprime:
\left .\begin{align}x\equiv a \bmod b \\x\equiv a \bmod c \end{align}\right\}\implies x\equiv a \bmod bc

Of interest: $561$ is the smallest Carmichael number

Apply the easy direction $(\Leftarrow)$ below, using $\,p_i\!-1 = 2,10,16\mid 560 = e\!-\!1\,$

Theorem  (Korselt's Carmichael Criterion) $\$ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree,\ \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n$$

Proof $\ \ (\Leftarrow)\ \$ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: \color{#c00}{a^{p-1} \equiv 1}\ \ ( mod\ p),\:$ by little Fermat, i.e.

$$\rm e\!-\!1 = k(p\!-\!1)\,\Rightarrow\, a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\qquad\qquad$$

$(\Rightarrow)\ \$ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \$ If $\rm\,n\,$ isn't squarefree then $\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$

$(2)\ \$ Let $\rm\ a\$ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$ Thus $\rm\ a\$ has order $\rm\:p\!-\!1.\:$ Now $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ but $\rm\:p\nmid a,\:$ thus $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ the order of $\rm\,\ a\,\ (mod\ p).\quad$ QED