1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hint: Use the Chinese remainder theorem. B.t.w., what does ‘proving a system of congruences’ mean? $\endgroup$ Commented Jul 27, 2017 at 16:35
  • $\begingroup$ Nothing, apparently. I guess since it involved three systems, and proofs, that that title made sense. $\endgroup$ Commented Jul 27, 2017 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$ Commented Jul 27, 2017 at 16:39
  • $\begingroup$ Possible duplicate of Why is $ 561 = 3*11*17 $ the smallest Carmichael number? $\endgroup$ Commented Nov 27, 2019 at 19:34

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.