RESIDUES – Part II

CONGRUENCES MODULO POWERS OF 2

Joseph B. Dence and Thomas P. Dence

A previous paper [1] summarized some theorems on cubic and quartic residues modulo an odd prime. These results may be regarded as extensions of corresponding theorems for quadratic residues modulo a prime. In the present paper we present, as the next logical step, some results on congruences modulo powers of the single prime 2. Certain of these results are formulas which are not well–known. They are not usually encountered in introductory number theory texts, but could form the basis for one or two lectures in a first course on number theory.

1. Quadratic Residues. A kth–power residue modulo m is an integer A ≠ 0 such that (A, m) = 1 and the congruence x^{k} ≡ A (mod m) is solvable [2]. The residues A in the cases of k = 2, 3, 4 are referred to as quadratic, cubic, and quartic residues, respectively, and if m = 2^{n} these residues are necessarily odd. For the remainder of this article we shall assume that A is a least positive residue, that is, 1 ≤ A < 2^{n}.

\underline{Theorem 1}. If A is a quadratic residue modulo 2^{n}, then A = 8k + 1, for some nonnegative integer k.

\underline{Proof}. The theorem is trivially true for n = 1, 2, and for A = 1, so assume n ≥ 3 and k > 0. Since A is odd, then any solution x_{0} of x^{2} ≡ A (mod 2^{n}) must be odd. Let x_{0} = 2j + 1; then x_{0}^{2} = 4j^{2} + 4j + 1 = 4j(j + 1) + 1 = 8m + 1, m > 0, since either j or j + 1 must be even. Hence, we have

8m + 1 ≡ A (mod 2^{n})

and as n ≥ 3, then A itself is of the form 8k + 1.

Table 1 gives all of the incongruent quadratic residues modulo 2^{7}, along with a solution x_{0} in each case, of x^{2} ≡ A (mod 2^{7}).

A  x_{0}  A  x_{0}
1  1  65  31
9  3  73  29
17  23  81  9
25  5  89  27
33  47  97  49
41  13  105  19
49  7  113  25
57  43  121  53

Table 1. Quadratic Residues Modulo 128

We notice that every A is of the form 8k + 1; this suggests the converse of Theorem 1.

\underline{Theorem 2}. If A = 8k + 1, k ≥ 0, then x^{2} ≡ A (mod 2^{n}) is solvable.

\underline{Proof}. By listing the particular cases, one can show that the theorem is true for 1 ≤ n ≤ 5; hence, assume that n ≥ 6. The theorem then holds trivially for A = 1; assume it also holds for A = A_{0} = 8k_{0} + 1, with n fixed, and that x = x_{0} is a solution in this case. Consider next

\begin{aligned}(3x_{0} + B · 2^{n−2})^{2} & ≡ 8(k_{0} + 1) + 1 (mod 2^{n}) \\ & ≡ A_{0} + 8 (mod 2^{n}), \end{aligned}

where B is to be determined. After expansion of the binomial on the left–hand side, we obtain

(3x_{0} · 2^{n−1})B ≡ 8(1 − A_{0}) (mod 2^{n}),

upon making use of 9x_{0}^{2} ≡ 9A_{0} (mod 2^{n}) and B^{2} · 2^{2n−4} ≡ 0 (mod 2^{n}), n ≥ 4. Let z = 2^{n−6} · B, so that the above congruence becomes

(96x_{0})z ≡ −64k_{0} (mod 2^{n}),

or

(3x_{0})z ≡ −2k_{0} (mod 2^{n−5}).

But as x_{0} is odd and (3x_{0}, 2^{n−5}) = 1, then this congruence has a unique solution z ≡ z_{0} (mod 2^{n−5}). It follows that B·2^{n−2} = 16z_{0}, and so x ≡ 3x_{0}+16z_{0} (mod 2^{n}) is a solution to x^{2} ≡ A_{0} + 8 (mod 2^{n}). The theorem then follows from the Principle of Mathematical Induction.

Thus, from Table 1 let A_{0} = 25, k_{0} = 3, x_{0} = 5. Then a solution of 15z ≡ −6 (mod 4) is z_{0} ≡ 2 (mod 4), and so x ≡ 15 + 16 · 2 ≡ 47 (mod 128) is a solution to x^{2} ≡ 33 (mod 128).

\underline{Corollary 2.1}. The number of incongruent quadratic residues modulo 2^{n} is 1 if n = 1 or 2, and \frac{1}{4}ϕ(2^{n}) = 2^{n−3} if n ≥ 3.

We may be interested to ascertain how often the congruence

x^{2} ≡ A (mod 2^{n})

is solvable, where A is even and 2 ≤ A < s^{n}. Any such values of A that permit a solution do not qualify as quadratic residues modulo 2^{n}, but let us write, nevertheless,

x^{2} ≡ 2^{a}r (mod 2^{n}),

where 2 ≤ 2^{a}r < 2^{n} and r is odd. If a is even, this reduces to u^{2} ≡ r (mod 2^{n−a}), and this is solvable if and only if r ≡ 1 (mod 2^{3}) from Theorems 1 and 2. If a is odd, the congruence becomes 2u^{2} ≡ r (mod 2^{n−a}), and this is not solvable. Hence, we have

\underline{Corollary 2.2}. The number of even integers A in the interval 2 ≤ A < 2^{n} for which x^{2} ≡ A (mod 2^{n}) is solvable is the number E_{2}(n) of integers of the form 2^{a}r, where 4 ≤ 2^{a}r < 2^{n}, a > 0 is even, and r = 8k + 1.

Some values of the number E_{2}(n) in Corollary 2.2 are listed in Table 2 for the first few n.

n  E_{2}(n)  n  E_{2}(n)
2  0  7  6
3  1  8  11
4  1  9  22
5  2  10  43
6  3  11  86

Table 2. Values of the Function E_{2}(n)

Given n, the number of allowed values of r in Corollary 2.2 is 2^{n−3}. The total number T_{n} of products 2^{a}r satisfying the conditions of Corollary 2.2 depends on whether n is odd or even. When n is odd we find by induction that

T_{n} = 1 + ∑_{k=0}^{(n−5)/2} 4^{k} = \frac{2 + 2^{n−3}}{3} (n ≥ 5),

and when n is even the result is

T_{n} = 1 + ∑_{k=0}^{(n−6)/2} 2 · 4^{k} = \frac{1 + 2^{n−3}}{3} (n ≥ 6).

These formulas are also accurate for n = 3, 4, respectively. Finally, combining these formulas with Corollary 2.1 gives

\underline{Corollary 2.3}. The number of integers A in the interval 1 ≤ A < 2^{n} for which x^{2} ≡ A (mod 2^{n}) is solvable is (2 + 2^{n−1})/3 when n ≥ 1 is odd, and is (1 + 2^{n−1})/3 when n ≥ 2 is even.

The contrast with the case when the modulus is a prime is startling. Thus, 2^{12} = 4096 has (1 + 2^{11})/3 = 683 integers A (of which, only 512 are actually quadratic residues) for which x^{2} ≡ A (mod 2^{12}) is solvable, whereas the nearest prime of 4093 has 2046 such integers A (all of which are quadratic residues).

2. Cubic Residues. An odd prime p has either p−1 or (p−1)/3 incongruent cubic residues, according as p = 3k + 2 or p = 3k + 1 [1]. The pattern is different when the modulus is 2^{n}, as the next theorem shows.

\underline{Theorem 3}. If k ≥ 3 is odd, then every odd A satisfying 1 ≤ A < 2^{n} is a kth–power residue modulo 2^{n}, for all n ∈ ℤ^{+}.

\underline{Proof}. Let \{x_{1}, x_{2}, …, x_{2^{n−1}}\} be the odd integers \{1, 3, …, 2^{n} − 1\}. Corresponding to each x_{i} we compute A_{i}, the least positive kth–power residue modulo 2^{n}. Suppose x_{i} ≠ x_{j} but A_{i} = A_{j}, for some i, j. Then

x_{i}^{k} − x_{j}^{k} ≡ 0 (mod 2^{n})

or

(x_{i} − x_{j})(x_{i}^{k−1} + x_{i}^{k−2}x_{j} + ⋯ + x_{j}^{k−1}) ≡ 0 (mod 2^{n}).

The binomial factor x_{i}−x_{j} is divisible by at most n−1 powers of 2 since x_{i}, x_{j} < 2^{n}. The polynomial factor is the sum of an odd number of odd terms and so is not divisible by 2. The contradiction implies A_{i} ≠ A_{j}, and therefore the A_{i}’s appear merely as a permutation of the x_{i}’s.

In an exercise, Rosen [3] asserts that our Theorem 3 holds, even if k is not odd. This assertion is false. For example, 3 is not a quartic residue modulo 8. Furthermore, Rosen’s “proof” begins by supposing 2^{n} to have a primitive root, which is false for n > 2.

Table 3 gives the least positive solution x_{0} to the congruence x^{3} ≡ A (mod 2^{n}) for n = 5 and for every odd A in the interval [1, 31]. We notice that x_{0}^{3} ≡ A (mod 2^{5}) implies A^{3} ≡ x_{0} (mod 2^{5}). This interesting behavior also holds for moduli 2, 4, 8, 16, but it is not general for moduli of the form 2^{n}.

A  x_{0}  A  x_{0}
1  1  17  17
3  27  19  11
5  29  21  13
7  23  23  7
9  25  25  9
11  19  27  3
13  21  29  5
15  15  31  31

Table 3. Cubic Residues Modulo 32

\underline{Theorem 4}. If A is odd and 1 ≤ A < 2^{n}, then x^{3} ≡ A (mod 2^{n}) implies A^{3} ≡ x (mod 2^{n}) only for n = 1, 2, 3, 4, 5.

\underline{Proof}. If x^{3} ≡ A (mod 2^{n}), then A^{3} ≡ (Ax)^{2}x (mod 2^{n}), so A^{3} ≡ x (mod 2^{n}) holds if and only if (Ax)^{2} ≡ 1 (mod 2^{n}), or x^{8} ≡ 1 (mod 2^{n}), for all odd x. This latter congruence holds for n = 4 from Euler’s theorem, and hence, also for n = 1, 2, 3. That it also holds for n = 5 follows from writing the congruence x^{8} ≡ 1 (mod 2^{5}) equivalently as

(x^{4} + 1)(x^{2} + 1)(x + 1)(x − 1) ≡ 0 (mod 2^{5}),

and noting that exactly one of the factors x + 1, x − 1 must be congruent to 0 (mod 4). However, 3^{8} ≢ 1 (mod 2^{n}) for all n ≥ 6. This proves the theorem.

Now consider even A that permit solutions of x^{3} ≡ A (mod 2^{n}). Write A = 2^{a}r, where 2 ≤ 2^{a}r < 2^{n} and r ≥ 1 is odd. By reasoning parallel to that used for Corollary 2.2, we deduce

\underline{Theorem 5}. The number of even integers A in the interval 2 ≤ A < 2^{n} for which x^{3} ≡ A (mod 2^{n}) is solvable is the number E_{3}(n) of integers of the form 2^{a}r, where 8 ≤ 2^{a}r < 2^{n}, 3|a, and 1 ≤ r is odd.

For comparison with the quadratic case, we list in Table 4 the values of the function E_{3}(n) in Theorem 5 for the first few n. For n ≥ 6 we have E_{3}(n) > E_{2}(n).

n  E_{3}(n)  n  E_{3}(n)
2  0  7  9
3  0  8  18
4  1  9  36
5  2  10  73
6  4  11  146

Table 4. Values of the Function E_{3}(n)

As with the quadratic case, the total number T_{n} of products 2^{a}r satisfying the conditions of Theorem 5 depends on the form of n. When n = 3k we find by induction that

T_{n} = ∑_{m=0}^{k−2} 4 · 8^{m} = \frac{2^{n−1} − 4}{7} (n ≥ 3),

when n = 3k − 1, then

T_{n} = ∑_{m=0}^{k−2} 2 · 8^{m} = \frac{2^{n−1} − 2}{7} (n ≥ 2),

and when n = 3k − 2, then

T_{n} = ∑_{m=0}^{k−2} 8^{m} = \frac{2^{n−1} − 1}{7} (n ≥ 4).

Combination of these formulas with Theorem 3 yields, analogous to Corollary 2.3,

\underline{Corollary 5.1}. The number of integers A in the interval 1 ≤ A < 2^{n} for which x^{3} ≡ A (mod 2^{n}) is solvable is

1,  if n = 1;
(2^{n+2} − 4)/7, if n = 3k;
(2^{n+2} − 2)/7, if n = 3k − 1;
(2^{n+2} − 1)/7, if n = 3k − 2.

Simple comparison shows that for all n > 1 the number of integers A in the interval 1 ≤ A < 2^{n} for which x^{3} ≡ A (mod 2^{n}) is solvable exceeds the number for which x^{2} ≡ A (mod 2^{n}) is solvable. This is possibly counter to intuition.

4. Quartic Residues. A result analogous to Theorems 1 and 2 holds for quartic residues and may be established by similar means.

\underline{Theorem 6}. The integer A is a quartic residue modulo 2^{n} if and only if A = 16k + 1 for k a nonnegative integer.

\underline{Proof}. (⇒) Suppose A_{0} is a quartic residue modulo 2^{n} and let x_{0} = 2j + 1 be a solution of x^{4} ≡ A_{0} (mod 2^{n}). Then

x_{0}^{4} = 16j^{4} + 32j^{3} + 24j^{2} + 8j + 1 = 8j(j + 1)(2j^{2} + 2j + 1) + 1 = 16m + 1, m > 0

(the case m = 0 is trivial). Hence, we have

16m + 1 ≡ A_{0} (mod 2^{n})

and as we may assume n ≥ 4 (because the lower cases can be disposed of directly), then A_{0} itself is of the form 16k + 1.

(⇐) The theorem can be shown directly to hold in this direction for n ≤ 7. Hence, assume n ≥ 8 and that the theorem holds for A = A_{0} = 16k_{0} + 1; let x_{0} be a solution in this case. We now consider

x^{4} ≡ A_{0} + 16 (mod 2^{n})

and set x = 3x_{0} + B · 2^{n−3}, where B is to be determined. Substitution and simplification yield

(27x_{0}^{3})z ≡ −1 − 20k_{0} (mod 2^{n−6}),

where z = B · 2^{n−7}. The congruence has a unique solution z ≡ z_{0} (mod 2^{n−6}) since (27x_{0}^{3}, 2^{n−6}) = 1. It follows that

x = 3x_{0} + 2^{4}(B · 2^{n−7}) = 3x_{0} + 16z_{0} (mod 2^{n})

is a solution to

x^{4} ≡ A_{0} + 16 (mod 2^{n}),

so the theorem holds by the Principle of Mathematical Induction.

\underline{Corollary 6.1}. The number of incongruent quartic residues modulo 2^{n} is 1 if n = 1, 2, 3, or 4, and \frac{1}{8}ϕ(2^{n}) = 2^{n−4} if n ≥ 5.

Alternatively, Theorem 6 and its corollary can be shown by an approach that is more algebraic in spirit. The set of incongruent kth–power residues modulo m form a group G_{k}(m) under modular multiplication. Corollary 2.1 states that |G_{2}(2^{n})| = 2^{n−3} if n ≥ 3. The quartic residues must be found among the members of G_{2}(2^{n}), and so by Lagrange’s theorem [4] one has |G_{4}(2^{n})| = 2^{k}, where the positive integer k ≤ n − 4 because 9, for example, is always a quadratic residue modulo 2^{n}, but is never a quartic residue modulo 2^{n}.

The integer 17 is a quartic residue modulo 2^{5}. Assume that it is also a quartic residue modulo 2^{n}, that is, there are integers x_{0}, k_{0} such that x_{0}^{4} − 17 = k_{0} · 2^{n}. Now let x = x_{0} + 2^{n−2}K, x^{4} ≡ 17 (mod 2^{n+1}), with K to be determined. The congruence reduces to

x_{0}^{3}K ≡ −k_{0} (mod 2),

which has a unique solution K_{0} modulo 2. It follows by the Principle of Mathematical Induction that 17 is a quartic residue modulo 2^{n} for all n ≥ 5.

The powers of 17 constitute a cyclic subgroup H_{4}(2^{n}) ⊆ G_{4}(2^{n}). What we want to do is show that 17 generates all of G_{4}(2^{n}).

\underline{Theorem 7}. |H_{4}(2^{n})| = |G_{4}(2^{n})| = 2^{n−4} if n ≥ 5.

\underline{Proof}. When n = 5, then
17^{2^{n−4}} ≡ 1 (mod 2^{n})

holds. Assume it also holds for n = k. Then

\begin{aligned}17^{2^{k−3}} − 1 & = (17^{2^{k−4}})^{2} − 1 \\ & = (17^{2^{k−4}} − 1)(17^{2^{k−4}} + 1) \end{aligned}

and as 2^{k} divides the first factor on the right by the induction hypothesis and 2 divides the second factor, then

17^{2^{k−3}} ≡ 1 (mod 2^{k+1}).

Hence, for any n ≥ 5 the order of H_{4}(2^{n}) does not exceed 2^{n−4}. The order of H_{4}(2^{n}) must be a power of 2, but the power 2^{n−5} is too small. From the Binomial Theorem we have

\begin{aligned}(16 + 1)^{2^{n−5}} − 1 & = 16^{2^{n−5}} + 2^{n−5}(16)^{2^{n−5}−1} + ⋯ + 2^{n−5}(16)^{1} \\ & = 2^{2^{n−3}} + 2^{2^{n−3}+n−9} + ⋯ + 2^{n−1}. \end{aligned}

Each term on the right except the last is divisible by 2^{n}, so

17^{2^{n−5}} ≢ 1 (mod 2^{n})

and |H_{4}(2^{n})| ≮ 2^{n−4}. It follows that |H_{4}(2^{n})| = 2^{n−4}, and since |G_{4}(2^{n})| cannot exceed 2^{n−4}, it must be that |H_{4}(2^{n})| = |G_{4}(2^{n})| = 2^{n−4} and the elements of G_{4}(2^{n}) are the numbers indicated in Theorem 6.

Comparing Corollaries 2.1 and 6.1, we see that for n ≥ 5 the number of incongruent quartic residues modulo 2^{n} is exactly half the number of incongruent quadratic residues modulo 2^{n}. A similar relationship was noted for moduli that are (4k + 1)–primes [1]. It may be remarked that this relationship between the sets of quadratic and quartic residues is not general for arbitrary moduli. Thus, the modulus 12 has identical sets of incongruent quadratic and quartic residues, namely, the singleton set {1}.

\underline{References}

1. J. B. Dence and T. P. Dence, “Cubic and Quartic Residues Modulo a Prime,” Missouri Journal of Mathematical Sciences, 7 (1995), 24–31.

2. T. Nagell, Introduction to Number Theory, John Wiley & Sons, New York, (1951), 115.

3. K. H. Rosen, Elementary Number Theory and its Applications, 3rd ed., Addison–Wesley, Reading, Massachusetts, (1993), 307.

4. J. B. Fraleigh, A First Course in Abstract Algebra, 5th ed., Addison–Wesley, Reading, Massachusetts, (1994), 121.

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

Thomas P. Dence Department of Mathematics Ashland University Ashland, OH 44805

æ