CYCLOTOMIC POLYNOMIALS AND PRIME NUMBERS

YVES GALLOT

Abstract. The sequence of numbers generated by the cyclotomic polynomials Φ_{n}(2) contains the Mersenne numbers 2^{p} − 1 and the Fermat numbers 2^{2^{m}} + 1. Does an algorithm involving O(n) modular operations exist to test the primality of Φ_{n}(b)?

1. Cyclotomic polynomials

Let n be a positive integer and let ζ_{n} be the complex number e^{2πi/n}. The n^{th} cyclotomic polynomial is, by definition

(1.1)  Φ_{n}(x) = ∏_{\begin{matrix}1≤k<n \\ gcd(k,n)=1 \end{matrix}}(x − ζ_{n}^{k})

Clearly the degree of Φ_{n}(x) is φ(n), where φ is the Euler function. We have

(1.2)  x^{n} − 1 = ∏_{d|n} Φ_{d}(x)

and conversely, by using the Möbius function, we can write

(1.3)  Φ_{n}(x) = ∏_{d|n}(x^{d} − 1)^{μ( \frac{n}{d})}.

Date: November 12, 2000; revised January 5, 2001. 2000 Mathematics Subject Classification. Primary 11Y11; Secondary 11A41. Key words and phrases. prime numbers, cyclotomic polynomials. (C) Copyright 2000, Yves Gallot. You may make unlimited copies of the document and give

copies to other persons as long as the copies you make and distribute contain the unaltered and unabridged document.

Φ_{n}(x) is a monic polynomial with integer coefficients. It can be shown that Φ_{n}(x) is irreductible over ℚ. The first sixteen of them are given below:

Φ_{1}(x) = x − 1  Φ_{2}(x) = x + 1
Φ_{3}(x) = x^{2} + x + 1  Φ_{4}(x) = x^{2} + 1
Φ_{5}(x) = x^{4} + x^{3} + x^{2} + x + 1  Φ_{6}(x) = x^{2} − x + 1
Φ_{7}(x) = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1 Φ_{8}(x) = x^{4} + 1
Φ_{9}(x) = x^{6} + x^{3} + 1  Φ_{10}(x) = x^{4} − x^{3} + x^{2} − x + 1
Φ_{11}(x) = x^{10} + x^{9} + x^{8} + ⋯ + x + 1  Φ_{12}(x) = x^{4} − x^{2} + 1
Φ_{13}(x) = x^{12} + x^{11} + x^{10} + ⋯ + x + 1 Φ_{14}(x) = x^{6} − x^{5} + x^{4} − x^{3} + x^{2} − x + 1
Φ_{15}(x) = x^{8} − x^{7} + x^{5} − x^{4} + x^{3} − x + 1 Φ_{16}(x) = x^{8} + 1

Theorem 1.1. If p is a prime then

Φ_{pm}(x) = Φ_{m}(x^{p}) when p divides m,
Φ_{pm}(x) = \frac{Φ_{m}(x^{p})}{Φ_{m}(x)} when p does not divide m.

Proof.

Φ_{pm}(x) = ∏_{\begin{matrix}d|pm \\ p|d \end{matrix}}(x^{d} − 1)^{μ( \frac{pm}{d})} ∏_{\begin{matrix}d|pm \\ p∤d \end{matrix}}(x^{d} − 1)^{μ( \frac{pm}{d})}

= Φ_{m}(x^{p}) ∏_{\begin{matrix}d|pm \\ p∤d \end{matrix}}(x^{d} − 1)^{μ( \frac{pm}{d})}

If p | m then \frac{pm}{d} = ap^{2} and μ(\frac{pm}{d}) = 0. If p ∤ m then μ(\frac{pm}{d}) = μ(p)μ(\frac{m}{d}) = −μ(\frac{m}{d}). □

It follows that if n_{1}, n_{2}, …, n_{k} are positive integers then

Φ_{n_{1}^{α_{1}} n_{2}^{α_{2}} ...n_{k}^{α_{k}}} (x) = Φ_{n_{1}·n_{2}...n_{k}}(x^{n_{1}^{α_{1}−1}n_{2}^{α_{2}−1}...n_{k}^{α_{k}−1}})

and if p is prime and r ≥ 1, then

Φ_{p^{r}}(x) = \frac{x^{p^{r}} − 1}{x^{p^{r−1}} − 1}.

Theorem 1.2. If q > 1 is an odd integer then

Φ_{2q}(x) = Φ_{q}(−x).

Proof.

Φ_{2q}(x) = ∏_{d|2q}(x^{d} − 1)^{μ( \frac{2q}{d})} = ∏_{d|q}(x^{d} − 1)^{μ( \frac{2q}{d})}(x^{2d} − 1)^{μ( \frac{2q}{2d})}

= ∏_{d|q}(x^{d} + 1)^{μ( \frac{q}{d})} = ∏_{d|q} −((−x)^{d} − 1)^{μ( \frac{q}{d})}.

If q ≠ 1 is odd then φ(q) is even. □

Theorem 1.3. If n > 1 then Φ_{n}(0) = 1.

Proof. By induction with x^{n} − 1 = Φ_{n}(x)(x − 1) ∏\begin{matrix}d|n \\ d≠1,n \end{matrix} Φ_{d}(x) and x = 0. □

Theorem 1.4. If n > 1 then

Φ_{n}(1) = p when n is a power of a prime p,
Φ_{n}(1) = 1 otherwise.

Proof. If n is not a prime power, let n = p^{r}m where p is prime and such that (p, m) = 1. Φ_{p^{r}m}(1) = Φ_{pm}(1^{r−1}) = \frac{Φ_{m}(1^{p})}{Φ_{m}(1)} and the result follows by induction because Φ_{m}(1) ≠ 0. □

2. Factors of Φ_{n}(b)

Theorem 2.1. Let n = p^{m} with p prime. If p | (b − 1) then p | Φ_{n}(b). All other prime factors of Φ_{n}(b) are of the form kn + 1.

Proof. See [8, Theorem 48]. □

The other forms can have some small factors: Φ_{18}(2) = 2^{6} − 2^{3} + 1 = 57 = 3 × 19 Φ_{20}(2) = 2^{8} − 2^{6} + 2^{4} − 2^{2} + 1 = 205 = 5 × 41 Φ_{21}(2) = 2^{12} − 2^{11} + 2^{9} − 2^{8} + 2^{6} − 2^{4} + 2^{3} − 2 + 1 = 2359 = 7 × 337 then Theorem 2.1 cannot be extended to any n. Theorem 2.2. Every prime factor of b^{n} − 1 must either be of the form kn + 1 or be a divisor of b^{d} − 1, where d < n and d | n.

Proof. See [9, Theorem 2.4.3]. □

Since Φ_{n}(b) | (b^{n} − 1), conditions of Theorem 2.2 are true for any factor of a cyclotomic polynomial, but we have a better result: Theorem 2.3. If p is a prime factor of Φ_{n}(b) and is a divisor of b^{d} − 1, where d < n, then p^{2} | (b^{n} − 1) and p | n.

Proof. [6] Let r > 0 such that p^{r} | (b^{n} − 1) but p^{r+1} ∤ (b^{n} − 1). If p^{r} | (b^{d} − 1) then p ∤ \frac{b^{n}−1}{b^{d}−1}. But by Eq.1.2, p | Φ_{n}(b) | \frac{b^{n}−1}{b^{d}−1}, a contradiction.

Let e_{r} the order of b modulo p^{r}. If p^{r} | (b^{m}−1) then e_{r} | m. Since p^{r} | (b^{e_{r+1}} −1), we have e_{r+1} = ke_{r}. Let b^{e_{r}} = 1+αp^{r}, then by the binomial theorem b^{ke_{r}} ≡ 1+αkp^{r} (mod p^{r+1}). If p | α, e_{r+1} = e_{r}, else p | k. Therefore either e_{r} = e_{1} = n (in which case n | (p − 1)) or p | n. □

Thus we have: Theorem 2.4. Every prime factor of Φ_{n}(b) must either be of the form kn + 1 or be a divisor of n and of b^{d} − 1, where d | n.

According to [7, Page 268], this result was proved by Legendre in 1830.

3. Primality test of Φ_{n}(b) by factoring Φ_{n}(b) − 1

From Theorem 1.3 we have Φ_{n}(x) − 1 = x^{r}P (x) where r ≥ 1. If r > deg(P)/2 and if the complete factorization of b is known then the primality of Φ_{n}(b) can be proved with theorems of [2]. Theorem 3.1. [3] If n = 2^{α}3^{β} then a theorem of Pocklington [2, Th 4][7, p. 52] is sufficient to test the primality of Φ_{n}(b) when b is factorized.

Proof. If β = 0 then Φ_{n}(b) − 1 = b^{2^{α}}. If α = 0 then Φ_{n}(b) − 1 = b^{3^{β−1}}(b^{3^{β−1}} + 1). Else Φ_{n}(b) = Φ_{6}(b^{2^{α−1}+3^{β−1}}) and Φ_{n}(b) − 1 = b^{2^{α−1}+3^{β−1}}(b^{2^{α−1}+3^{β−1}} − 1). □

No other case of polynomial factorization by x^{r} large enough is known: Conjecture 3.2. [3] If Φ_{n}(x) − 1 = x^{r}P (x) and n ≠ 2^{α}3^{β} then r < deg(P)/2.

Note that if n has many divisors, Φ_{n}(b) − 1 has often enough polynomial factors to complete the primality proof for some small b. See [4] for criteria of divisibility of Φ_{n}(x) − 1 by Φ_{k}(x).

Note also the generalization of the well-known results about Fermat and Mersenne numbers 2^{F_{m}−1} ≡ 1 (mod F_{m}) and 2^{M_{p}−1} ≡ 1 (mod M_{p}): Theorem 3.3. If Φ_{n}(b) has no prime factor p ≤ n then b^{Φ_{n}(b)−1} ≡ 1 (mod Φ_{n}(b)).

Proof. By Eq.1.2, b^{Φ_{n}(b)−1} − 1 = ∏_{d|(Φ_{n}(b)−1)} Φ_{d}(b). By Theorem 2.4, if Φ_{n}(b) has no prime factor p ≤ n then Φ_{n}(b) = kn+1. Therefore Φ_{n}(b) divides b^{Φ_{n}(b)−1}−1. □

4. Primes of the form Φ_{n}(2)

If n = 2^{m} then Φ_{2^{m}}(2) = 2^{2^{m−1}} + 1 = F_{m−1} (Fermat number). If p is prime then Φ_{p}(2) = 2^{p} − 1 = M_{p} (Mersenne number). If p ≠ 2 then Φ_{2p}(2) = Φ_{p}(−2) = (2^{p} + 1)/3.

The first probable primes of the form Φ_{n}(2) were computed by the author. The primality of these numbers was proved for n ≤ 3000 by the author with the implementation of Adleman-Pomerance-Rumely-Cohen-Lenstra’s test of the UBASIC package [5] and for 3000 < n ≤ 6500 by Phil Carmody with Titanix [1] (see Table 1 and Table 2).

Fermat and Mersenne primes are two sparse subclasses of the dense class of the primes of the form Φ_{n}(2). But how to prove the primality of Φ_{n}(2) with only O(n) operations modulo Φ_{n}(2) when n is not a prime or a power of 2?

Table 1. Values of n for which Φ_{n}(2) is prime, for 1 ≤ n ≤ 6500

2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 19, 22, 24, 26, 27, 30, 31, 32, 33, 34, 38, 40, 42, 46, 49, 56, 61, 62, 65, 69, 77, 78, 80, 85, 86, 89, 90, 93, 98, 107, 120, 122, 126, 127, 129, 133, 145, 150, 158, 165, 170, 174, 184, 192, 195, 202, 208, 234, 254, 261, 280, 296, 312, 322, 334, 345, 366, 374, 382, 398, 410, 414, 425, 447, 471, 507, 521, 550, 567, 579, 590, 600, 607, 626, 690, 694, 712, 745, 795, 816, 897, 909, 954, 990, 1106, 1192, 1224, 1230, 1279, 1384, 1386, 1402, 1464, 1512, 1554, 1562, 1600, 1670, 1683, 1727, 1781, 1834, 1904, 1990, 1992, 2008, 2037, 2203, 2281, 2298, 2353, 2406, 2456, 2499, 2536, 2838, 3006, 3074, 3217, 3415, 3418, 3481, 3766, 3817, 3927, 4167, 4253, 4423, 4480, 5053, 5064, 5217, 5234, 5238, 5250, 5325, 5382, 5403, 5421, 6120.

References

1. Marcel Martin, Titanix: a primality prover using the Goldwasser, Kilian and Atkin algorithm, 2000, http://www.znz.freesurf.fr/

2. J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New Primality Criteria and Factorizations of 2^{m} ± 1, Math. Comp. 29 (1975), 620–647.

3. D. Broadhurst, communication to PrimeForm egroup, 2000.

Table 2. Values of n for which Φ_{n}(2) is a probable prime, for 6500 ≤ n ≤ 44497

6925, 7078, 7254, 7503, 7539, 7592, 7617, 7648, 7802, 7888, 7918, 8033, 8370, 9583, 9689, 9822, 9941, 10192, 10967, 11080, 11213, 11226, 11581, 11614, 11682, 11742, 11766, 12231, 12365, 12450, 12561, 13045, 13489, 14166, 14263, 14952, 14971, 15400, 15782, 15998, 16941, 17088, 17917, 18046, 19600, 19937, 20214, 20678, 21002, 21382, 21701, 22245, 22327, 22558, 23209, 23318, 23605, 23770, 24222, 24782, 27797, 28958, 28973, 29256, 31656, 31923, 33816, 34585, 35565, 35737, 36960, 39710, 40411, 40520, 42679, 42991, 43830, 43848, 44497.

4. C. K. Caldwell, Unique (period) primes and the factorization of cyclotomic polynomials minus one, Mathematica Japonica 26:1 (1997), 189–195.

5. Yuji Kida, UBASIC: a BASIC with ultra-fast multi-precision arithmetic, 1989, http://archives.math.utk.edu/software/msdos/number.theory/ubasic/

6. C. Nash, private communication, 1999.

7. P. Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag, New York, 1995.

8. D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed., Chelsea, New York, 1993.

9. H.C. Williams, Edouard Lucas and Primality Testing, A Wiley-Interscience publication, Canadian Mathematical Society series of monographs, 1998.