Extension of Fermat's little theorem with Carmichael numbers
If $a$ and $b$ are coprime and $a\mid n$ and $b\mid n$, then $ab\mid n$
Note that $561=3\times11\times17$
Now suppose we can show that $a^{561}-a$ is divisible by $3$ and $11$ and $17$, if this is true, then sense $3,11$ and $17$ are coprime, we have $a^{561}-a$ is divisible by $3\times11\times17=561$, so that $a^{561}-a\equiv 0 \text{ mod 561}$, or $$a^{561}\equiv a \text{ mod 561}$$
Thus you need only show $a^{561}\equiv a \text{ mod p}$ for the primes $3,11$ and $17$
Related videos on Youtube
Alex
Updated on August 01, 2022Comments
-
Alex over 1 year
I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this congruence is not always true from my understanding as having $a^n \not\equiv a \;(\!\!\!\mod n)$ provides that $n$ is not prime in the case that this occurs so the equivalence may not always be true. The question is however prefaced by the given $n$ being a Carmichael number though. Could anyone hint at how I should approach this explanation?
The Problem
The number 561 factors as $3 \cdot 11 \cdot 17$. First use Fermat's little theorem to prove that \begin{equation*} a^{561} \equiv a \;(\!\!\!\mod{3}), \quad a^{561} \equiv a \;(\!\!\!\mod{11}), \quad a^{561} \equiv a \;(\!\!\!\mod{17}) \end{equation*} for every value of $a$. Then explain why these three congruences imply that $a^{561} \equiv a \;(\!\!\!\mod{561})$ for every value of $a$.
Current Solution
Fermat's little theorem states that given a prime $p$, for every $a\in(\mathbb{Z}/p\mathbb{Z})^{\ast}$, \begin{equation*} a^{p-1} \equiv 1 \;(\!\!\!\mod{p}). \end{equation*} Then by Fermat's little theorem, \begin{equation*} a^{561} = a^{2\cdot28}a = \big(a^{28}\big)^2a \equiv a \;(\!\!\!\mod{3}), \end{equation*} \begin{equation*} a^{561} = a^{56 \cdot 10}a = \big(a^{56}\big)^{10}a \equiv a \;(\!\!\!\mod{11}), \end{equation*} \begin{equation*} a^{561} = a^{35\cdot16}a = \big(a^{35}\big)^{16}a \equiv a \;(\!\!\!\mod{17}). \end{equation*}
-
Andreas Blass over 10 yearsHow did you get the equation $\big(a^{187}\big)^3\equiv a\pmod 3$? Fermat's little theorem gives you that $\big(a^{187}\big)^3\equiv a^{187}\pmod 3$. Another angle on the same issue: Your proof doesn't seem to use anything special about 561; wouldn't an analogous argument for any other integer be equally (un)justified?
-
Alex over 10 yearsDidn't notice that fault. Will start reworking what I have done, thank you.
-
Alex over 10 years@AndreasBlass Would you mind telling me if my statement for $a^{187} \equiv a \mod 3$ makes sense or if I have incorrectly applied Fermat's little theorem?
-
Andreas Blass over 10 yearsYes, $a^{187}\equiv a\pmod 3$ makes sense and it's even true. So are the two analogous equations that you need mod 11 and 17. But you need to prove them, not just take my word for them.
-
Alex over 10 yearsI meant to ask if this made sense to show the congruence: $a^{187} = a^{3\cdot62}a^1 \equiv a^{62}a^1 = a^{3\cdot21} \equiv a^{21}=a^{3\cdot7}\equiv a^7 = a^{2\cdot3}a^1 \equiv a^2a^1 = a^3 \equiv a \mod 3$
-
Andreas Blass over 10 yearsThis computation looks correct but excessively complicated. I'd begin by noting that what you want to prove is clear if $a\equiv0\pmod 3$, so you can concentrate on the case of $a\not\equiv0\pmod3$. In this case, you have, as an easy reformulation of the little Fermat theorem, that $a^2\equiv1\pmod3$, and this can be used for a much shorter calculation.
-