Extension of Fermat's little theorem with Carmichael numbers

3,025

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$

Share:
3,025

Related videos on Youtube

Alex
Author by

Alex

Updated on August 01, 2022

Comments

  • Alex
    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
      Andreas Blass over 10 years
      How 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
      Alex over 10 years
      Didn't notice that fault. Will start reworking what I have done, thank you.
    • Alex
      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
      Andreas Blass over 10 years
      Yes, $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
      Alex over 10 years
      I 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
      Andreas Blass over 10 years
      This 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.