Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having some trouble with this proof and I need some help heading down the right direction:

Suppose $n = p_1p_2 \cdots p_k$ where $p_i$ are distinct primes and that $p_i - 1 \mid n - 1$. Show that $n$ is a Carmichael number, that is, that $a^{n - 1} \equiv 1 \pmod n$ for all $a$ with $\gcd(a, n) = 1$.

Thank you for your help.

share|improve this question
1  
Hint: $x \equiv y \mod n$ iff $x \equiv y \mod p_i$ for all $i$. –  Chris Eagle Nov 18 '11 at 13:04
1  
I think I understand. So the solution is basically using this fact and Fermat's little theorem to show that $a^{p_i-1} \equiv 1 (mod p_i)$ for all $p_i$? –  TheEnigmaMachine Nov 18 '11 at 14:53
    
You can find full proofs of Korselt's criterion and generalizations in the links of my post here. Note: some sci.math links need to change from "google.com/..." to "groups.google.com/..." to work nowadays. –  Bill Dubuque Nov 18 '11 at 16:41

1 Answer 1

Actually much stronger is true. We have that

For $n > 2$, $n$ is Carmichael if and only if $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i - 1 \mid n - 1$ for every $i$.

The proof is as follows

Assume $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i - 1 \mid n - 1$ for every $i$. For $b \in \Bbb{Z}$, we have that, if $p_i \mid b$,then $b^n \equiv 0 \equiv b \pmod{p_i}$ and if $p_i \nmid b$,then $b^{n - 1} \equiv b^{(p_1 -1)\ell} \equiv 1 \pmod{p_i}$. So $b^{n} \equiv b \pmod{p_i}$. Therefore by the Chinese Remainder Theorem, $$ b^n \equiv b \pmod{n} $$ and hence $n$ is Carmichael.

Conversely suppose that $n$ is Carmichael. First we will prove that $n$ is squarefree. Assume by contradiction that it is not squarefree. Then there exists some integer $v$ such that $v^2 \mid n$. Now we have that $v^n \equiv v \pmod{n}$ since $n$ is Carmichael. So this implies that $n \mid v^n - v$. Since $v^2 \mid v^n$ (since $n$ is Carmichael, it is composite and hence $n > 2$) and $v^2 \mid n$ we have that $v^2 \mid v$ which is impossible. So $n$ is squarefree. Since $n$ is squarefree, $n = p_1 \cdots p_k$ for distinct primes $p_i$.

Since $n$ is Carmichael, we have that $$ b^n \equiv b \pmod{n} $$ for all integers $b$ such that $gcd(b, n) = 1$. Therefore $b^{n-1} \equiv 1 \pmod{n}$. So we have that $ord_n(b)$ divides $n - 1$. In particular we have that the universal exponent of $U_n$, which we denote $\kappa_n$, where $U_n$ is the unit group of $\Bbb{Z}/n\Bbb{Z}$, which consists of all the elements in $\Bbb{Z}/n\Bbb{Z}$ that are coprime to $n$, divides $n-1$. Since $$ \kappa_n = lcm (\kappa_{p_i}) = lcm(p_i - 1) $$ we have that $p_i - 1 \mid n-1$ for all $i$. This completes our proof.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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