MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 fix

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? 3 added 151 characters in body; added 2 characters in body; added 37 characters in body 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.

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

2 edited tags
1