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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.