ON A SYMMETRIC FUNCTION OF THE PRIMITIVE ROOTS OF PRIMES

Joseph B. Dence and Thomas P. Dence

1. Introduction. The elementary symmetric functions of n variables are:

s_{1} = u_{1} + u_{2} + ⋯ + u_{n}
s_{2} = u_{2}u_{1} + u_{3}u_{1} + u_{3}u_{2} + ⋯ + u_{n}u_{n−1} = ∑_{i>j} u_{i}u_{j}

s_{3} = ∑_{i>j>k} u_{i}u_{j}u_{k}

⋮

s_{n} = ∏_{i=1}^{n} u_{i}.

In a previous paper [1] we investigated the elementary symmetric function s_{1} of the primitive roots of a prime. The principal tool was the use of certain cyclotomic polynomials. The present work continues this line of investigation and considers the function s_{2} of the primitive roots. Throughout, p denotes an odd prime, d ≥ 1 is any divisor of p − 1, and {g_{i}} is the set of primitive roots of p.

2. Numerical Results. The first few odd primes, beginning with p = 5, yield the following simple results: p = 5: s_{2} ≡ 1 (mod p); p = 7: s_{2} ≡ 1 (mod p); p = 11: s_{2} ≡ 1 (mod p); p = 13: s_{2} ≡ −1 (mod p); p = 17: s_{2} ≡ 0 (mod p). The residues obtained strongly urge the computation of the residues modulo p of s_{2} for many more primes. A sampling of these computations is given in Table 1. Since in [1] it was important to note whether p − 1 is squarefree or not, Table 1 has been organized so that the primes p in columns (1)–(3) are those where p − 1 is not squarefree; in columns (4) and (5) p − 1 is squarefree.

\begin{aligned}& (1) \\ p & s_{2} (mod p) \\ 5 & 1 \\ 61 & 1 \\ 277 & 1 \\ 373 & 1 \\ 4621 & 1 \end{aligned}  \begin{aligned}& (2) \\ p & s_{2} (mod p) \\ 19 & 0 \\ 37 & 0 \\ 73 & 0 \\ 193 & 0 \\ 457 & 0 \end{aligned}  \begin{aligned}& (3) \\ p & s_{2} (mod p) \\ 29 & -1 \\ 53 & -1 \\ 293 & -1 \\ 421 & -1 \\ 797 & -1 \end{aligned}

\begin{aligned}& (4) \\ p & s_{2} (mod p) \\ 31 & 0 \\ 43 & 0 \\ 67 & 0 \\ 79 & 0 \\ 683 & 0 \end{aligned}  \begin{aligned}& (5) \\ p & s_{2} (mod p) \\ 23 & 1 \\ 47 & 1 \\ 59 & 1 \\ 83 & 1 \\ 463 & 1 \end{aligned}

Table 1. Residues of the Symmetric Function s_{2} of the Primitive Roots of Various Primes p.

The table suggests strongly that for all primes p ≥ 5 the congruence

s_{2} ≡ 0 or ± 1 (mod p)

holds. Our object is to show this by making a connection with s_{1}.

3. Sums of Squares of the Primitive Roots. The connection with s_{1} is made by considering the sums of squares of the primitive roots. Let

S = ∑_{i=1}^{ϕ(p−1)} g_{i}^{2};

then it follows algebraically that 2s_{2} = s_{1}^{2}−S, and we need the residues modulo p of S in order to compute the residues modulo p of s_{2}. We do this by again appealing to certain properties of the cyclotomic polynomials.

The nth cyclotomic polynomial, Φ_{n}(x), is defined as

Φ_{n}(x) = ∏_{ζ}(x − ζ),

where ζ spans all of the primitive nth roots of unity. We recall that the degree of Φ_{n}(x) is ϕ(n), and all of the coefficients in Φ_{n}(x) are integers [4]. Write

Φ_{n}(x) = ∑_{k=0}^{ϕ(n)} c(n, k)x^{k},

as in [1]. Then if n = d, a divisor of p − 1, Theorem 3 in [1] shows that the coefficient c(d, ϕ(n)−1) is 0 if d is not squarefree, +1 if d is squarefree and contains an odd number of prime factors, and −1 if d = 1 or d is squarefree and contains an even number of prime factors. Since the roots of Φ_{d}(x) ≡ 0 (mod p) are all of the incongruent integers of order d modulo p, the preceding gives us Theorem 1 [6].

\underline{Theorem 1}. The sum of the incongruent integers of order d modulo p is congruent to μ(d), where μ is the Möbius function.

In particular, Theorem 1 gives immediately for any odd prime p,

s_{1} ≡ μ(p − 1) (mod p).

But from [2], for any g_{i}, the integer g_{i}^{2} has order

\frac{p − 1}{(2, p − 1)} = \frac{p − 1}{2}.

There are

ϕ(\frac{p − 1}{2})

incongruent integers of order (p − 1)/2, whereas there are ϕ(p − 1) primitive roots. Hence, squaring and reducing the primitive roots modulo p produces

\frac{ϕ(p − 1)}{ϕ(\frac{p−1}{2})}

copies of the integers of order d = (p − 1)/2. Theorem 2 follows from this and from Theorem 1.

\underline{Theorem 2}.

S ≡ \frac{ϕ(p − 1)}{ϕ(\frac{p−1}{2})}μ(\frac{p − 1}{2}) (mod p),

if p is any odd prime.

A more general result than Theorem 2 was stated in [5]. It is clear that the residues of S are restricted to 0, ±1, ±2. We illustrate this in Table 2.

\begin{matrix}p & ϕ(p − 1) & ϕ((p − 1)/2) & μ((p − 1)/2) & S & S (mod p) \\ 11 & 4 & 4 & -1 & 153 & -1 \\ 41 & 16 & 8 & 0 & 8036 & 0 \\ 53 & 24 & 12 & 1 & 21944 & 2 \\ 61 & 16 & 8 & -1 & 20372 & -2 \\ 79 & 24 & 24 & 1 & 61937 & 1 \\ 211 & 48 & 48 & -1 & 848008 & -1 \end{matrix}

Table 2. Residues Modulo p of the Sums of Squares of the Primitive Roots of Various Primes p.

4. The Main Result. In view of the relationship between s_{1}, s_{2} and S, and of the result in Theorem 2, the following theorem emerges.

\underline{Theorem 3}. Let \{g_{i}\} denote the primitive roots of the prime p ≥ 5, and let

Φ_{p−1}(x) = ∑_{k=0}^{ϕ(p−1)} c(p − 1, k)x^{k}

be the (p − 1)st cyclotomic polynomial. Then

\begin{aligned}s_{2} = ∑_{i>j} g_{i}g_{j} & ≡ c(p − 1, ϕ(p − 1) − 2) (mod p) \\ & ≡ \frac{1}{2}((μ(p − 1))^{2} − \frac{ϕ(p − 1)}{ϕ(\frac{p−1}{2})}μ(\frac{p − 1}{2})) (mod p). \end{aligned}

That the right–hand side of the last congruence is actually integral can be seen by considering various cases of factorization of p − 1, (1/2)(p − 1).

The formula in Theorem 3 can be presented pictorially (in Figure 1) by considering, in fact, the different cases of factorization of p − 1, (1/2)(p − 1). There are precisely five such cases of factorization; these correspond to the five columns of Table 1.

As a matter of distribution, we observe that among the first 100 primes (beginning with p = 5) the residues −1, 0, 1 of s_{2} occur in the ratios 12 : 59 : 29. The question of what these ratios should be in the limit of infinitely many primes is an interesting one.

Finally, we note in conclusion that although Theorem 3 might be generalizable to an arbitrary elementary symmetric function s_{n} and to an arbitrary modulus (but one which still has primitive roots), the result is apt to be too complex to permit a simple pictorial presentation analogous to Figure 1. This has long been suspected [3].

\underline{References}

1. J. B. Dence, “Primitive Roots the Cyclotomic Way,” Missouri Journal of Mathematical Sciences, 12 (1999), 5–11.

2. J. B. Dence and T. P. Dence, Elements of the Theory of Numbers, Harcourt/Academic Press, San Diego, California, 1999.

3. A. R. Forsyth, “Primitive Roots of Prime Numbers and Their Residues,” Messenger of Mathematics, 13 (1883/1884), 169–192.

4. L. J. Goldstein, Abstract Algebra, Prentice–Hall, Englewood Cliffs, New Jersey, 1973, 226–227.

5. R. Moller, “Sums of Powers of Numbers Having a Given Exponent Modulo a Prime,” American Mathematical Monthly, 59 (1952), 226–230.

6. M. A. Stern, “Bemerkungen über hohere Arithmetik,” Journal für Mathematik, 6 (1830), 147–153.

Joseph B. Dence Department of Chemistry University of Missouri St. Louis, MO 63121

Thomas P. Dence Department of Mathematics Ashland University Ashland, OH 44805 email: tdence@ashland.edu

Figure 1.

Classification of the Primes on the Basis of the Residues Modulo p of the Symmetric Function s_{2}.