31.8 Primality testing

31.8-1

Prove that if an odd integer \(n > 1\) is not a prime or a prime power, then there exists a nontrivial square root of \(1\) modulo \(n\).

(Omit!)

31.8-2 \(\star\)

It is possible to strengthen Euler's theorem slightly to the form

\(a^{\lambda(n)} \equiv 1 \pmod n\) for all \(a \in \mathbb Z_n^\*\),

where \(n = p_1^{e_1} \cdots p_r^{e_r}\) and \(\lambda(n)\) is defined by

\[\lambda(n) = \text{lcm}(\phi(p_1^{e_1}), \ldots, \phi(p_r^{e_r})). \tag{31.42}\]

Prove that \(\lambda(n) \mid \phi(n)\). A composite number \(n\) is a Carmichael number if \(\lambda(n) \mid n - 1\). The smallest Carmichael number is \(561 = 3 \cdot 11 \cdot 17\); here, \(\lambda(n) = \text{lcm}(2, 10, 16) = 80\), which divides \(560\). Prove that Carmichael numbers must be both "square-free" (not divisible by the square of any prime) and the product of at least three primes. (For this reason, they are not very common.)

1. Prove that \(\lambda(n) \mid \phi(n)\).

   We have

   \[ \begin{aligned} n & = p_1^{e_1} \cdots p_r^{e_r} \\\\ \phi(n) & = \phi(p_1^{e_1}) \times \dots \times \phi(p_r^{e_r}). \end{aligned} \]

   Thus,

   \[ \begin{aligned} \lambda(n) & \mid \phi(n) \\\\ \Rightarrow \text{lcm}(\phi(p_1^{e_1}, \ldots, \phi(p_r^{e_r})) & \mid (\phi(p_1^{e_1}) \times \dots \times \phi(p_r^{e_r})) \end{aligned} \]

2. Prove that Carmichael numbers must be "square-free" (not divisible by the square of any prime).

   Assume \(n = p^\alpha m\) is a Carmichael number, where \(\alpha \ge 2\) and \(p \nmid m\).

   By the Chinese Remainder Theorem, the system of congruences

   \[ \begin{aligned} x & \equiv 1 + p \pmod p^\alpha, \\\\ x & \equiv 1 \pmod m \end{aligned} \]

   has a solution \(a\). Note that \(\gcd(a, n) = 1\).

   Since \(n\) is a Carmichael number, we have \(a^{n - 1} \equiv 1 \pmod n\). In particular, \(a^{n - 1} \equiv 1 \pmod {p^\alpha}\); therefore, \(a^n \equiv a \pmod {p^2}\).

   So, \((1 + p)^n \equiv 1 + p \pmod {p^2}\). Expand \((1 + p)^n\) modulo \(p^2\) using the binomial theorem. We have

   \[(1 + p)^n \equiv 1 \pmod {p^2},\]

   since the first two terms of the expansion are \(1\) and \(np\), and the rest of the terms are divisible by \(p^2\).

   Thus, \(1 \equiv 1 + p \pmod {p^2}\). This is impossible.

   Stack Exchange Reference

3. Prove that Carmichael numbers must be the product of at least three primes.

   Assume that \(n = pq\) is a Carmichael number, where \(p\) and \(q\) are distant primes and \(p < q\).

   Then we have

   \[ \begin{aligned} & q \equiv 1 \pmod{q - 1} \\\\ \Rightarrow & n \equiv pq \equiv p \pmod{q - 1} \\\\ \Rightarrow & n - 1 \equiv p - 1 \pmod{q - 1}, \end{aligned} \]

   Here, \(0 < p − 1 < q − 1\) , so \(n − 1\) is not divisible by \(q − 1\).

   Stack Exchange Reference

31.8-3

Prove that if \(x\) is a nontrivial square root of \(1\), modulo \(n\), then \(\gcd(x - 1, n)\) and \(\gcd(x + 1, n)\) are both nontrivial divisors of \(n\).

\(n \mid (x + 1)(x - 1)\), suppose \(\gcd(x - 1, n) = 1\), then \(n \mid (x + 1)\), then \(x \equiv -1 \pmod n\) which is trivial, it contradicts the fact that \(x\) is nontrivial, therefore \(\gcd(x - 1, n) \ne 1\), \(\gcd(x + 1, n) \ne 1\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用