TAOCP 4.5.4 Exercise 9

Let $n$ be an odd integer with $n \ge 3$, and let $\lambda(n)$ be the Carmichael function of $n$, as defined in Theorem 3.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.4: Factoring into Primes

Exercise 9. [M25] Let $n$ be an odd number, $n \ge 3$. Show that if the number $\lambda(n)$ of Theorem 3.2.1.2B is a divisor of $n - 1$ but not equal to $n - 1$, then $n$ must have the form $p_1 p_2 \ldots p_r$ where the $p$'s are distinct primes and $r \ge 3$.

Verified: yes
Solve time: 2m28s

Solution

Let $n$ be an odd integer with $n \ge 3$, and let $\lambda(n)$ be the Carmichael function of $n$, as defined in Theorem 3.2.1.2B. By definition, $\lambda(n)$ is the smallest positive integer such that

$a^{\lambda(n)} \equiv 1 \pmod{n}$

for all $a$ with $\gcd(a,n) = 1$. Suppose $\lambda(n) \mid (n-1)$ but $\lambda(n) \ne n-1$. We aim to determine the prime factorization of $n$ under this condition.

Since $n$ is odd, its prime factorization can be written uniquely as

$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r},$

where $p_1 < p_2 < \cdots < p_r$ are odd primes, and $\alpha_i \ge 1$ for all $i$.

Recall that for an odd prime power $p^\alpha$, the Carmichael function satisfies

$\lambda(p^\alpha) = (p-1)p^{\alpha-1}.$

Moreover, $\lambda$ is multiplicative over relatively prime factors:

$\lambda(n) = \operatorname{lcm}(\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \ldots, \lambda(p_r^{\alpha_r})).$

If $r = 1$, then $n = p_1^{\alpha_1}$ is a prime power. In this case,

$\lambda(n) = (p_1 - 1) p_1^{\alpha_1 - 1}.$

For $\lambda(n)$ to divide $n-1 = p_1^{\alpha_1} - 1$, it must be that

$(p_1 - 1) p_1^{\alpha_1 - 1} \mid p_1^{\alpha_1} - 1.$

However,

$p_1^{\alpha_1} - 1 = (p_1 - 1)(p_1^{\alpha_1 - 1} + p_1^{\alpha_1 - 2} + \cdots + 1).$

The factor $p_1^{\alpha_1 - 1}$ in $\lambda(n)$ cannot divide the sum

$S := p_1^{\alpha_1 - 1} + p_1^{\alpha_1 - 2} + \cdots + 1$

unless $\alpha_1 = 1$, since $\gcd(p_1^{\alpha_1 - 1}, S) = 1$ for $\alpha_1 > 1$. Thus $\alpha_1 = 1$, so $n = p_1$ is prime. Then $\lambda(n) = p_1 - 1 = n - 1$, which contradicts the assumption $\lambda(n) \ne n-1$. Therefore $r \ge 2$.

Suppose $r = 2$, so $n = p_1^{\alpha_1} p_2^{\alpha_2}$. Then

$\lambda(n) = \operatorname{lcm}(\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2})) = \operatorname{lcm}((p_1-1)p_1^{\alpha_1-1}, (p_2-1)p_2^{\alpha_2-1}).$

Since $p_1$ and $p_2$ are distinct primes, $p_1$ does not divide $(p_2-1)p_2^{\alpha_2-1}$ and $p_2$ does not divide $(p_1-1)p_1^{\alpha_1-1}$. Therefore, $\operatorname{lcm}((p_1-1)p_1^{\alpha_1-1}, (p_2-1)p_2^{\alpha_2-1})$ is divisible by $p_1 p_2$, whereas

$n-1 = p_1^{\alpha_1} p_2^{\alpha_2} - 1$

is congruent to $-1$ modulo $p_1$ and modulo $p_2$. Thus $\lambda(n)$ cannot divide $n-1$ if $r = 2$.

Consequently, $r \ge 3$.

Finally, all prime exponents $\alpha_i$ must equal 1. If $\alpha_i > 1$ for any $i$, then $p_i$ divides $\lambda(n)$ as before, but $p_i$ does not divide $n-1 = n - 1$ because $n \equiv 0 \pmod{p_i}$ implies $n-1 \equiv -1 \not\equiv 0 \pmod{p_i}$. This is impossible. Therefore $n$ is squarefree.

In summary, $n$ must be a product of at least three distinct primes:

$n = p_1 p_2 \cdots p_r, \qquad r \ge 3,$

with $p_i$ distinct odd primes. This completes the proof.

∎