Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|cite|improve this question
Do show that $n$ is square-free. – Emil Jeřábek Mar 15 '12 at 14:08
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 – KConrad Mar 15 '12 at 14:17

1 Answer 1

up vote 0 down vote accepted

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.

share|cite|improve this answer
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$. – Emil Jeřábek Mar 16 '12 at 14:38
And, please, do not post comments as answers. – Emil Jeřábek Mar 16 '12 at 14:41
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$. – Emil Jeřábek Mar 16 '12 at 15:04
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. – laerne Mar 17 '12 at 9:42
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 to merge your existing accounts. – Emil Jeřábek Mar 17 '12 at 17:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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