CUBIC AND QUARTIC RESIDUES MODULO A PRIME

Joseph B. Dence

University of Missouri–St. Louis

Thomas P. Dence

Ashland University

1. Residues Modulo A Prime. Standard theorems on quadratic residues form an integral part of any introductory course on the theory of numbers. Seldom is much material presented on residues of higher order. Let p be a prime and let the integer a satisfy 1 ≤ a < p. Then a is said to be a kth order residue of p (or modulo p) if the congruence

x^{k} ≡ a (mod p)

has a solution. For example, 6 is a cubic residue (3rd order residue) of 7 since 3^{3} ≡ 6 (mod 7).

Here, we summarize some elementary theorems about cubic and quartic (4th order) residues of prime moduli. The following theorem is central [1,2].

\underline{Theorem 1}. x^{k} ≡ a (mod p) has a solution if and only if a^{(p−1)/d} ≡ 1 (mod p), where d = (k, p − 1). If the congruence has a solution, then it actually has d incongruent solutions modulo p.

\underline{Proof}. Since p is a prime, it has a primitive root, say r [2]. Then from index arithmetic we have that x^{k} ≡ a (mod p) holds if and only if

k · ind_{r}x ≡ ind_{r}a (mod p − 1).

Let d = (k, p − 1) and z = ind_{r}x, that is, x ≡ r^{z} (mod p). Then the congruence kz ≡ ind_{r}a (mod p − 1) has no solutions (z) or d incongruent solutions modulo p − 1 if and only if d -| ind_{r}a or d | ind_{r}a, respectively. Hence, x^{k} ≡ a (mod p) has d incongruent solutions modulo p if and only if d | ind_{r}a or if and only if (p − 1)ind_{r}a = n(p − 1)d for some n ∈ ℤ^{+}. This is equivalent to a^{(p−1)/d} ≡ 1 (mod p) since ind_{r}1 = 0.

The theorem is a generalization of Euler’s Criterion for quadratic residues.

2. Cubic Residues. Throughout this section k = 3. When p = 5, 7, 11, 13, 17, 19 and 23, the number of cubic residues of these primes are 4, 2, 10, 4, 16, 6 and 22, respectively. A pattern is evident.

\underline{Theorem 2}. The number of cubic residues of p > 3 is (p − 1)/3 or p − 1, depending on whether p is of the form 3j + 1 or 3j + 2, respectively.

\underline{Proof}. If p = 3j + 1, then d = (k, p − 1) = (3, 3j) = 3, so from Theorem 1, a is a cubic residue of p if and only if a^{(p−1)/3} − 1 ≡ 0 (mod p). Lagrange’s Theorem [3,4] says that in ℤ_{p} this polynomial congruence has at most (p − 1)/3 solutions. However, a related theorem says that if m | (p − 1), then the congruence x^{m} − 1 ≡ 0 (mod p) has the full set of m solutions [4]. Thus, since (p − 1)/3 | (p − 1), then a^{(p−1)/3} − 1 ≡ 0 (mod p) has exactly (p − 1)/3 solutions in ℤ_{p}.

If p = 3j + 2, then d = (k, 3j + 1) = (3, 3j + 1) = 1 and a is a cubic residue to p if and only if a^{(p−1)} ≡ 1 (mod p). This holds for all a satisfying 1 ≤ a ≤ p − 1 by Fermat’s Theorem, so there are p − 1 cubic residues of p.

We let S_{p}^{(3)} denote the set of cubic residues of the prime p. The sets S_{p}^{(3)} for the first few primes are shown in Table 1.

\begin{matrix}p & 2 & 3 & 5 & 7 & 11 & 13 \\ S_{p}^{(3)} & \{1\} & \{1, 2\} & \{1, 2, 3, 4\} & \{1, 6\} & \{1, 2, ⋯, 10\} & \{1, 5, 8, 12\} \end{matrix}

TABLE 1. Cubic Residues of the First Few Primes

These sets have algebraic structure. We recall that an element α of a field F is an nth root of unity if α^{n} = 1.

\underline{Theorem 3}. The cubic residues of a prime p form a multiplicative group.

\underline{Proof}. Let F be any field and U_{n} the set of all nth roots of unity in F. If α^{n} = 1, β^{n} = 1, then (αβ)^{n} = α^{n}β^{n} = 1, so field multiplication is closed on U_{n}. Associativity is inherited from F. Now let α ∈ U_{n} be arbitrary, and define τ = α^{n−1}. Then ατ = τα = α^{n} = 1, so every element in U_{n} has a multiplicative inverse and U_{n} is therefore a group. In particular, let F = ℤ_{p} and p = 3j + 1. Then from Theorems 1 and 2, U_{n} is S_{p}^{3}, the set of all jth roots of unity. If F = ℤ_{p} and p = 3j + 2, then U_{n} is S_{p}^{(3)}, the set of all (3j + 1)st roots of unity.

Thus, we see from Table 1 that in ℤ_{7} the set S_{7}^{(3)} is the set of two square roots of 1, and in ℤ_{13} the set S_{13}^{(3)} is the set of four fourth roots of 1. We also observe from Table 1 that for p > 2, |S_{p}^{(3)}| is even. For when p = 3j + 2, then |S_{p}^{(3)}| = p − 1, and when p = 3j + 1 is prime, then p is actually of the form 6j + 1, so (p − 1)/3 = 2j is even. It is also obvious that S_{p}^{(3)} is a cyclic group since it is either U_{j} or U_{3j+1}, corresponding to p = 3j + 1 or p = 3j + 2. The cyclic nature of S_{p}^{(3)} also follows from the observation that S_{p}^{(3)} is a subgroup of ℤ_{p}^{∗}, the multiplicative group of all nonzero elements of the finite field ℤ_{p}, and this latter group is cyclic [5,6].

\underline{Corollary 3.1}. S_{p}^{(3)} is a cyclic group of even order for p > 2.

The following theorem shows that if some of the cubic residues of a prime p are known, it is possible to deduce some additional ones.

\underline{Theorem 4}. If a is a cubic residue of p, then so is p − a.

\underline{Proof}. Suppose p = 3j + 1 and a ∈ S_{p}^{(3)}; then a^{(p−1)/3} ≡ 1 (mod p). Next, since (p − 1)/3 is even, then (p − a)^{(p−1)/3} ≡ (−a)^{(p−1)/3} ≡ a^{(p−1)/3} ≡ 1 (mod p), so p − a ∈ S_{p}^{(3)}. On the other hand, if p = 3j + 2, then (p − a)^{p−1} ≡ (−a)^{p−1} ≡ a^{p−1} ≡ 1 (mod p), and thus in this case, also, p − a ∈ S_{p}^{(3)}.

The following two corollaries are immediate from Theorem 4. We let T_{p}^{(3)} denote the sum of all the members of S_{p}^{(3)}.

\underline{Corollary 4.1}. If p > 2, the elements in S_{p}^{(3)} occur in pairs, where the sum of the members of any pair is p.

\underline{Corollary 4.2}. For all primes p ≥ 5 one has

T_{p}^{(3)} = \{ \begin{matrix}jp, & if p = 6j + 1 \\ (3j + 1)p/2, & if p = 3j + 2. \end{matrix}

For example, let p = 43 = 6 · 7 + 1. The cubic residues of 43 are found to be 1, 2, 4, 8, 11, 16, 21, 22, 27, 32, 35, 39, 41, 42; their sum is 301 = 7 · 43. In either case in the second corollary we have that T_{p}^{(3)} is an integral multiple of p.

That p | T_{p}^{(3)} can be obtained in still another way. Let m = |S_{p}^{(3)}|, where m is either (p − 1)/3 or p − 1. Then m | (p − 1) and therefore in ℤ_{p} the congruence x^{m} − 1 ≡ 0 (mod p) has its full complement of roots and from [4], we can write

x^{m} − 1 ≡ (x − a_{1})(x − a_{2}) ⋯ (x − a_{m}) (mod p).

We see immediately that

coefficient of x^{m−1} = − ∑_{i=1}^{m} a_{i} ≡ 0 (mod p)

coefficient of x^{m−2} = ∑_{i<j} a_{i}a_{j} ≡ 0 (mod p),

and so on. The first congruence gives us p | T_{p}^{(3)}.

\underline{Corollary 4.3}. Let A_{p}^{(3)} denote the sum of the squares of all the members of S_{p}^{(3)}. Then for p = 5 and all primes p > 7, one has p | A_{p}^{(3)}.

\underline{Proof}. Denote the members of S_{p}^{(3)} by a_{1}, a_{2}, …, a_{m}, where m is either (p − 1)/3 or p − 1. Then write

A_{p}^{(3)} = a_{1}^{2} + a_{2}^{2} + ⋯ + a_{m}^{2}

= (a_{1} + a_{2} + ⋯ + a_{m})^{2} − 2 ∑_{i<j} a_{i}a_{j}

= [T_{p}^{(3)}]^{2} − 2 ∑_{i<j} a_{i}a_{j}.

Corollary 4.2 gives us p | [T_{p}^{(3)}]^{2}, and the discussion prior to Corollary 4.3 gives us p | ∑_{i<j} a_{i}a_{j}, so p | A_{p}^{(3)}.

Corollary 4.3 fails for p = 3, 7 because these are the only values of p for which S_{p}^{(3)} = {1, p − 1}, so A_{p}^{(3)} = p^{2} − 2p + 2 and thus p -| (p^{2} − 2p + 2).

Finally, we look at one multiplicative property of cubic residues. We let P_{p}^{(3)} denote the product of all the members of S_{p}^{(3)}.

\underline{Theorem 5}. 1 + P_{p}^{(3)} ≡ 0 (mod p).

\underline{Proof}. The theorem is obviously true when p = 2. When p > 2, the congruence x^{2} ≡ 1 (mod p) has the solutions x ≡ 1 (mod p) and x ≡ p − 1 (mod p). In view of Theorem 3, each element a_{i} ∈ S_{p}^{(3)} except 1, p − 1 has an inverse a_{j} distinct from itself. Hence,

∏_{a_{i}∈S_{p}^{(3)}} a_{i} ≡ p − 1 (mod p),

or P_{p}^{(3)} ≡ p − 1 (mod p), which is equivalent to 1 + P_{p}^{(3)} ≡ 0 (mod p).

3. Quartic Residues. We denote the set of all quartic residues of a prime p by S_{p}^{(4)}, and the set of all quadratic residues of p by S_{p}^{(2)}. Every quartic residue a is automatically a quadratic residue since if x^{4} ≡ a (mod p) has a solution, then y^{2} ≡ a (mod p) also holds, where y = x^{2}. Thus, S_{p}^{(4)} ⊆ S_{p}^{(2)} and we may find all members of S_{p}^{(4)} by squaring the elements of S_{p}^{(2)}.

By Euler’s Criterion, a is a quadratic residue of p (p ≥ 3) if and only if

a^{(p−1)/2} ≡ 1 (mod p),

whereas from Theorem 1 we have that a is a quartic residue of p if and only if

a^{(p−1)/d} ≡ 1 (mod p),

where d = (4, p − 1). For p ≥ 3 one has d = 2 or 4. When d = 2 the sets S_{p}^{(2)}, S_{p}^{(4)} are identical, whereas when d = 4 one has |S_{p}^{(4)}| = (1/2)|S_{p}^{(2)}|. Accordingly, we obtain as the analog of Theorem 2 (for p ≥ 3).

\underline{Theorem 6}. The number of quartic residues of p is (p − 1)/4 or (p − 1)/2, depending on whether p > 2 is of the form 4j + 1 or 2j + 1 (j odd), respectively, and in either case |S_{p}^{(4)}| = j.

The argument of Theorem 3 carries over unaltered to quartic residues. Further, the algebraic argument preceding Corollary 3.1 that was used to show the cyclic nature of S_{p}^{(3)} also applies to S_{p}^{(4)}.

\underline{Theorem 7}. The quartic residues of a prime p form a cyclic group under modular multiplication.

Unlike the case with S_{p}^{(3)}, the order of S_{p}^{(4)} may be either odd or even. Table 2 shows the first few cases.

\begin{matrix}p & 2 & 3 & 5 & 7 & 11 & 13 \\ S_{p}^{(4)} & \{1\} & \{1\} & \{1\} & \{1, 2, 4\} & \{1, 3, 4, 5, 9\} & \{1, 3, 9\} \end{matrix}

TABLE 2. Quartic Residues of the First Few Primes

When (p − 1)/4 is not an integer, then (p − 1)/2 is an odd integer. Thus, for primes p = 3, 7, 11, 19, 23, and so on, S_{p}^{(4)} is a group of odd order. When (p − 1)/4 is an integer, it may be either odd or even. Clearly, we have \underline{Corollary 7.1}. S_{p}^{(4)} is a cyclic group of even order if and only if p = 8j + 1. According to Theorem 4, p − 1 is always a cubic residue of p. In contrast, from

Theorem 1 we see that p − 1 is a quartic residue if and only if (p − 1)/d is even, where d = (k, p − 1) = (4, p − 1). But now Corollary 7.1 has told us just when (p − 1)/d is even, so

\underline{Corollary 7.2}. p − 1 is a quartic residue of p if and only if p = 8j + 1.

The algebraic argument following Corollary 4.2 allows one to also say p | T_{p}^{(4)}, where T_{p}^{(4)} stands for the sum of all the members of S_{p}^{(4)}. Alternately, since S_{p}^{(4)} is cyclic, it has a generator g. From Theorem 6 we have |S_{p}^{(4)}| = j for p = 4j + 1 or p = 2j + 1. The elements of S_{p}^{(4)} can thus be listed modulo p as {g^{0}, g^{1}, g^{2}, ⋯, g^{j−1}}, where g^{0} = 1. Then, if g ≠ 1,

\begin{aligned}T_{p}^{(4)} & = 1 + g^{1} + g^{2} + ⋯ + g^{j−1} \\ & = \frac{g^{j} − 1}{g − 1}. \end{aligned}

Since S_{p}^{(4)} has order j, then g^{j} ≡ 1 (mod p). It follows that T_{p}^{(4)} ≡ 0 (mod p). \underline{Theorem 8}. For p > 5 one has p | T_{p}^{(4)}. Note the requirement that p > 5. When p = 2, 3, or 5, the only quartic residue is 1,

this being so in the last case because of Fermat’s Theorem.

In x^{4} ≡ a (mod p), as one runs through the nonzero members x of ℤ_{p}, a symmetry in the occurrence of the quartic residues a is observed. For example, notice the following distribution in the case of p = 11.

\begin{matrix}x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ a & 1 & 5 & 4 & 3 & 9 & 9 & 3 & 4 & 5 & 1 \end{matrix}

TABLE 3. Symmetry Between Elements of ℤ_{11} and the Corresponding Quartic Residues

\underline{Theorem 9}. If the quartic residue corresponding to x ∈ ℤ_{p} is a, then the quartic residue corresponding to p − x is also a.

\underline{Proof}. Direct computation gives

\begin{aligned}(p − x)^{4} & = p^{4} − 4p^{3}x + 6p^{2}x^{2} − 4px^{3} + x^{4} \\ & ≡ 0 − 0 + 0 − 0 + a (mod p). \end{aligned}

We denote by P_{p}^{(4)} the product of all the members of S_{p}^{(4)}. For example, from Table 2 we have

P_{11}^{(4)} = 1 · 3 · 4 · 5 · 9 = 540 ≡ 1 (mod 11),

whereas for p = 17,

P_{17}^{(4)} = 1 · 4 · 13 · 16 = 832 ≡ −1 (mod 17).

\underline{Theorem 10}. For all p one has

P_{p}^{(4)} ≡ \{ \begin{matrix}−1 (mod p), & if p = 8j + 1 \\ +1 (mod p), & otherwise. \end{matrix}

\underline{Proof}. The theorem is obviously true when p = 2, 3, 5. When p ≥ 7 is not of the form 8j + 1, |S_{p}^{(4)}| is odd and the only member of S_{p}^{(4)} which is its own inverse is 1 by Corollaries 7.1, 7.2. In this case, the members of S_{p}^{(4)}, where |S_{p}^{(4)}| = 2n + 1, can be paired as follows

{ 1 ; a_{1} ↔ a_{1}^{−1} ; a_{2} ↔ a_{2}^{−1} ; a_{3} ↔ a_{3}^{−1} ; ⋮ ; a_{n} ↔ a_{n}^{−1}

and hence,

P_{p}^{(4)} = 1 · ∏_{i=1}^{n} a_{i} · a_{i}^{−1} ≡ 1 (mod p).

On the other hand, if p = 8j + 1, then |S_{p}^{(4)}| is of even order, p − 1 is an element of S_{p}^{(4)}, where |S_{p}^{(4)}| = 2n + 2, and from the arrangement

{ 1 ; a_{1} ↔ a_{1}^{−1} ; a_{2} ↔ a_{2}^{−1} ; a_{3} ↔ a_{3}^{−1} ; ⋮ ; a_{n} ↔ a_{n}^{−1} ; p − 1

we obtain

P_{p}^{(4)} = 1 · (∏_{i=1}^{n} a_{i} · a_{i}^{−1}) · (p − 1) ≡ p − 1 ≡ −1 (mod p).

Theorem 10 contrasts with Theorem 5. Note also that Theorem 8 is almost analogous to Corollary 4.3

\underline{References}

1. H. E. Rose, A Course in Number Theory, Oxford University Press, Oxford, (1988), 83–84.

2. K. H. Rosen, Elementary Number Theory and Its Applications, 3rd ed., Addison– Wesley, Reading, (1993), 285–302.

3. T. M. Apostol, Introduction to Analytic Number Theory, Springer, New York, (1976), 115.

4. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford University Press, Oxford, (1979), 84–85.

5. J. B. Fraleigh, A First Course in Abstract Algebra, 4th ed., Addison–Wesley, Reading, (1989), 408–409.

6. M. Artin, Algebra, Prentice–Hall, Englewood Cliffs, (1991), 510–513. æ