MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

closed as off-topic by Stefan Kohl, Ryan Budney, Scott Morrison Dec 9 '15 at 0:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Stefan Kohl, Ryan Budney
If this question can be reworded to fit the rules in the help center, please edit the 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
I'm closing this question as off-topic; it has been answered in the comments. – Scott Morrison Dec 9 '15 at 0:20
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

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.

share|cite|improve this answer

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