1
$\begingroup$

I would like to prove the equivalence of the two most common definitions of a composite integer $n > 1$ being a Carmichael number: $a^n \equiv a \mod n $ for all $a$ $\iff a^{n-1} \equiv 1 \mod n$ for all $a$ such that $\mathrm{gcd}(a,n)=1$.

I do not see how to prove the right-to-left statement (that is, why if the congruence on the right holds whenever $\mathrm{gcd}(a,n)=1$ then the congruence on the left holds for all $a$). Of course if $n$ divides $a$, the congruence on the left is obvious since both terms are 0.

I would like to use the Chinese remainder theorem to try to reduce the problem to the case of a prime-power modulus $n = p^e$ (since I don't know yet $n$ must be square-free), but $a^{n-1} \equiv 1 \mod{p^e}$ is not a very helpful equation.

Every article on the web says it is obvious, but not for me. Can you help me?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Do show that $n$ is square-free. $\endgroup$
    – Emil Jeřábek
    Commented Mar 15, 2012 at 14:08
  • 2
    $\begingroup$ From the condition on the right, prove n satisfies Korselt's criterion. (Look in any book that discusses Carmichael numbers for a proof.) In particular, you can write $n=p_1...p_r$ with distinct primes $p_i$. To prove two integers are congruent mod $n$, check they're congruent modulo each $p_i$. So we want to show for every $a$ that $a^n\equiv a \bmod p_i$ for all $i$. Write this as $a(a^{n−1}−1)\equiv 0 \bmod p_i$. Since $p_i−1$ is a factor of $n−1$ (by Korselt), if gcd($a$,$p_i$)=1 then $a^{n-1}\equiv 1 \bmod p_i$,and if gcd($a$,$p_i$)>1 then $p_i|a$ so $a \equiv 0 \bmod p_i$. QED $\endgroup$
    – KConrad
    Commented Mar 15, 2012 at 14:17
  • $\begingroup$ I'm closing this question as off-topic; it has been answered in the comments. $\endgroup$
    – Kim Morrison
    Commented Dec 9, 2015 at 0:20

2 Answers 2

Reset to default
0
$\begingroup$

Korselt's criterion uses that $p^n = p$ for any $p|n$, but $(p,n)=p\ne 1$, so I still don't see to get ou of this. Maybe my proof of Korselts's criterion is out of date.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Let $p^k\mid n$, $p^{k+1}\nmid n$, $k>1$. Let $a\equiv1+p^{k-1}\pod{p^k}$, $(a,n)=1$. Then $a^p\equiv1\pod{p^k}$ by computation and $a^{n-1}\equiv1\pod{p^k}$ by assumption, which gives $a\equiv1\pod{p^k}$. This contradiction shows that $n$ is square-free. If $p\mid n$, let $g$ be a multiplicative generator of $\mathbb F_p$, so that $g^k\equiv1\pod p$ iff $p-1\mid k$. Take $a\equiv g\pod p$, $(a,n)=1$. Then $g^{n-1}\equiv a^{n-1}\equiv1\pod p$, hence $p-1\mid n-1$. $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2012 at 14:38
  • 2
    $\begingroup$ And, please, do not post comments as answers. $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2012 at 14:41
  • $\begingroup$ Also, in order to show the equivalence in the OP, you only need that $n$ is square-free, not the rest of Korselt’s criterion. It suffices to show $a^n\equiv a\pod p$ for every prime $p\mid n$. If $p\mid a$, then both sides are zero. Otherwise, there is $b\equiv a\pod p$, $(b,n)=1$, hence $a^{n-1}\equiv b^{n-1}\equiv1\pod p$ and $a^n\equiv a\pod p$. $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2012 at 15:04
  • $\begingroup$ Thank you very, I begin to see the pattern of the proof. Though I do not need Korselt Criterion, I shall prove it on the run, so it's done. But one big problem remains for me : why do $(a,n)=1$ ? for instance if $n$ would be $p^k(1+p^{k-1})$, the statement would be wrong since $a|n$. Of course such a $n$ is not a caermichael number for $k \ge 2$ since it is not square-free, but that's what I want to prove ! Finding coprimes is a recurring issue I cannot get rid of. PS: Sorry for the answer, I use another account to answer. I didn't understand you can recover an account. $\endgroup$
    – laerne
    Commented Mar 17, 2012 at 9:42
  • $\begingroup$ If you are referring to the $a$ in my proof, you choose it so that it is coprime to $n$. You can do this by the Chinese remainder theorem: for instance, there is an $a$ such that $a\equiv1+p^{k-1}\pod{p^k}$ and $a\equiv1\pod{n/p^k}$; such an $a$ is necessarily coprime to $n$. You can avoid problems with involuntary creation of multiple accounts if you register, and you can ask on tea.mathoverflow.net to merge your existing accounts. $\endgroup$
    – Emil Jeřábek
    Commented Mar 17, 2012 at 17:46
-2
$\begingroup$

The obvious step you're missing is this: If a^(n-1) = 1 (mod p^e), simply multiply both sides of the congruence by a.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .