bzprules wrote: Let $n\in\mathbb{N}$ be given. Prove that the following two conditions are equivalent: $\quad(\text{i})\: n|a^n-a$ for any positive integer $a$; $\quad(\text{ii})\:$ For any prime divisor $p$ of $n$, $p^2 \nmid n$ and $p-1|n-1$. http://en.wikipedia.org/wiki/Carmichael_number

bzprules wrote: Let $n\in\mathbb{N}$ be given. Prove that the following two conditions are equivalent: $\quad(\text{i})\: n|a^n-a$ for any positive integer $a$; $\quad(\text{ii})\:$ For any prime divisor $p$ of $n$, $p^2 \nmid n$ and $p-1|n-1$. I suppose we have to prove, so the link of wikipedia is not the contest question: Take $g$ primitive root of $p$ which has $gcd(n,g)=1$ (easy that is possible with CRS), then $p|g^{n-1}-1$ and so $p-1|n-1.$ Then LTE gives $v_p((g^{(p-1)})^{\frac{n-1}{p-1}}-1)=1$ In reverse order, by FLT it follows.

Assume $(i)$ is true. Assume for contradiction that for $p\mid n$ we have $p^2\mid n$. If we take $a=p$, we get a contradiction. So $p^2 \nmid n$. Now let $p\mid n$ be a prime. We have $a^n \equiv a \pmod{p}$. Now take $a$ to be a primitive root modulo $p$, then we get $a^{n-1} \equiv 1 \pmod{p} \implies p-1\mid n-1$. Now the first part is proven. For the second part, easy applications of FLT suffices. So we are done.