Revisions - MathOverflow

Return to Question

fix

view source

edited Mar 15 2012 at 14:06

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 \bmod mod n $ for all $a$ $\iff a^{n-1} \equiv 1 \bmod 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 right 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 a^{n-1} \equiv 1 \bmod p^e$ 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?

added 151 characters in body; added 2 characters in body; added 37 characters in body

view source

edited Mar 15 2012 at 13:59

KConrad
17.2k●3●64●119

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

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

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