most recent 30 from http://mathoverflow.net 2013-05-23T20:03:01Z http://mathoverflow.net/feeds/question/91277 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91277/equivalence-of-definitions-of-carmichael-numbers laerne 2012-03-15T13:39:20Z 2012-03-16T14:14:51Z

<p>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$. </p> <p>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.</p> <p>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.</p> <p>Every article on the web says it is obvious, but not for me. Can you help me?</p>

http://mathoverflow.net/questions/91277/equivalence-of-definitions-of-carmichael-numbers/91372#91372 laerne 2012-03-16T14:14:51Z 2012-03-16T14:14:51Z

<p>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.</p>