Representing Integers as the Sum of Two Squares in the Ring ℤ_{n}

Joshua Harrington, Lenny Jones, and Alicia Lamarche Department of Mathematics Shippensburg University Shippensburg, PA 17257 USA

                 JSHarrington@ship.edu
                    lkjone@ship.edu
                    al5903@ship.edu

Abstract

A classical theorem in number theory due to Euler states that a positive integer z can be written as the sum of two squares if and only if all prime factors q of z, with q ≡ 3 (mod 4), occur with even exponent in the prime factorization of z. One can consider a minor variation of this theorem by not allowing the use of zero as a summand in the representation of z as the sum of two squares. Viewing each of these questions in ℤ_{n}, the ring of integers modulo n, we give a characterization of all integers n ≥ 2 such that every z ∈ ℤ_{n} can be written as the sum of two squares in ℤ_{n}.

1 Introduction

We begin with a classical theorem in number theory due to Euler [5]. Theorem 1. A positive integer z can be written as the sum of two squares if and only if all prime factors q of z with q ≡ 3 (mod 4) occur with even exponent in the prime factorization of z.

Euler’s complete proof of Theorem 1 first appeared in a letter to Goldbach [5], dated April 12, 1749. His proof uses a technique known as the method of descent [2], which was first used by Fermat to show the nonexistence of nontrivial solutions to certain Diophantine equations. Note that, according to Theorem 1, the positive integer 9, for example, can be written as the sum of two squares. Since there is only one way to write 9 as the sum of two squares, namely 9 = 3^{2} + 0^{2}, we conclude that 0^{2} is allowed as a summand in the representation as the sum of two squares for the integers described in Theorem 1. So, a somewhat natural question to ask is the following.

Question 2. What positive integers z can be written as the sum of two nonzero squares?

A complete answer to Question 2 does not seem to appear in the literature. However, a partial answer is given by the following classical result [2, Thm. 367 and Thm. 368, pp. 299–300].

Theorem 3. Let n > 1 be an integer. Then there exist u, v ∈ ℤ, with gcd(u, v) = 1, such that n = u^{2} + v^{2} if and only if −1 is a quadratic residue modulo n.

While it is not our main concern in this article, we nevertheless provide, for the sake of completeness, an answer to Question 2 in the same flavor as Theorem 1. The next two results [2, 3] are well-known, and so we omit the proofs. The first of these results is originally due to Diophantus.

Lemma 4. The set of positive integers that can be written as the sum of two squares is closed under multiplication.

Lemma 4 allows us to establish the following partial answer to Question 2.

Proposition 5. Let p ≡ 1 (mod 4) be a prime, and let a be a positive integer. Then there exist nonzero squares x^{2} and y^{2} such that p^{a} = x^{2} + y^{2}.

To provide a complete answer to Question 2, we let Z denote the set of all integers described in Theorem 1, and we ask the following, somewhat convoluted, question.

Question 6. Which integers z ∈ Z actually do require the use of zero when written as the sum of two squares?

Certainly, the integers z that answer Question 6 are squares themselves, and therefore we have that z = c^{2}, for some positive integer c, and no integers a > 0 and b > 0 exist with z = c^{2} = a^{2} + b^{2}. In other words, \sqrt{z} is not the third entry in a Pythagorean triple (a, b, c). Pythagorean triples (a, b, c) can be described precisely in the following way.

Theorem 7. The triple (a, b, c) is a Pythagorean triple if and only if there exist integers k > 0 and u > v > 0 of opposite parity with gcd(u, v) = 1, such that

a = (u^{2} − v^{2})k, b = (2uv)k and c = (u^{2} + v^{2})k.

Thus, we have the following.

Theorem 8. Let Ẑ be the set of positive integers that can be written as the sum of two nonzero squares. Then z ∈ Ẑ if and only if z ∈ Z, and if z is a perfect square, then \sqrt{z} = (u^{2} +v^{2})k for some integers k > 0 and u > v > 0 of opposite parity with gcd(u, v) = 1.

However, a closer look reveals a somewhat more satisfying description for the integers z ∈ Ẑ in Theorem 8, similar in nature to the statement of Theorem 1.

Theorem 9. Let Ẑ be the set of positive integers that can be written as the sum of two nonzero squares. Then z ∈ Ẑ if and only if all prime factors q of z with q ≡ 3 (mod 4) have even exponent in the prime factorization of z, and if z is a perfect square, then z must be divisible by some prime p ≡ 1 (mod 4).

Proof. Suppose first that z ∈ Ẑ. Then z ∈ Z and all prime factors q of z with q ≡ 3 (mod 4) have even exponent in the prime factorization of z by Theorem 1. So, suppose that z = c^{2} for some positive integer c, and assume, by way of contradiction, that z is divisible by no prime p ≡ 1 (mod 4). By Theorem 8, we can write c = (u^{2} + v^{2}) k for some integers k > 0 and u > v > 0 of opposite parity with gcd(u, v) = 1. Since no prime p ≡ 1 (mod 4) divides z, we have that no prime p ≡ 1 (mod 4) divides u^{2} + v^{2}. Note that u^{2} + v^{2} is odd, and so every prime q dividing u^{2} + v^{2} is such that q ≡ 3 (mod 4). Thus, by Theorem 1, every prime divisor of u^{2} + v^{2} has even exponent in the prime factorization of u^{2} + v^{2}. In other words, u^{2} + v^{2} is a perfect square. Hence, u^{2} + v^{2} ∈ Ẑ, and by Theorem 8, we have that

\sqrt{u^{2} + v^{2}} = (u_{1}^{2} + v_{1}^{2}) k_{1},

for some integers k_{1} > 0 and u_{1} > v_{1} > 0 of opposite parity with gcd(u_{1}, v_{1}) = 1. We can repeat this process, but eventually we reach an integer that is the sum of two distinct squares that has a prime factor q ≡ 3 (mod 4) that occurs to an odd power in its prime factorization. This contradicts Theorem 1, and completes the proof in this direction.

If z is not a perfect square and every prime factor q of z with q ≡ 3 (mod 4) has even exponent in the prime factorization of z, then z can be written as the sum of two squares by Theorem 1; and moreover, these squares must be nonzero since z is not a square itself. Thus, z ∈ Ẑ in this case. Now suppose that z is a perfect square and z is divisible by some prime p ≡ 1 (mod 4). Let z = p^{2e} ∏_{i=1}^{t} r_{i}^{2e_{i}} be the canonical factorization of z into distinct prime powers. By Proposition 5, there exist integers u > v > 0, such that p^{2e} = u^{2} + v^{2}. Then

z = (u ∏_{i=1}^{t} r_{i}^{e_{i}})^{2} + (v ∏_{i=1}^{t} r_{i}^{e_{i}})^{2} ∈ Ẑ,

and the proof is complete.

Remark 10. The method of proof used to establish the first half of Theorem 9 is reminiscent of Fermat’s method of descent [2].

In this article, we move the setting from ℤ to ℤ_{n}, the ring of integers modulo n, and we investigate a modification of Question 2 in this new realm. Investigations of variations of Question 2, when viewed in ℤ_{n}, do appear in the literature. For example, Fine [1] asked if rings other than ℤ satisfy one, or both, of the following slightly-generalized conditions of Theorem 3:

1. If r ∈ R and −1 is a quadratic residue modulo r, then r = ± (u^{2} + v^{2});

2. If r = u^{2} + v^{2} with gcd(u, v) = 1, then −1 is a quadratic residue modulo r.

In particular, Fine showed that ℤ_{n} satisfies condition 2., and that ℤ_{p^{a}} satisfies both condition 1. and 2., when p ≡ 3 (mod 4) is prime and a ≥ 2.

Another variation of Question 2 viewed in ℤ_{n} was considered by Wegmann [6]. For any k ∈ ℤ_{n}, he determined the least positive integer s such that the congruence

k ≡ x_{1}^{2} + x_{2}^{2} + ⋯ + x_{s}^{2} (mod n),

is solvable with x_{i} ∈ ℤ_{n}.

In this article, we are concerned with another variation of Question 2 in ℤ_{n}. In our investigations, we discovered for certain values of n that every element in ℤ_{n} can be written as the sum of two nonzero squares. It is our main goal to characterize, in a precise manner, these particular values of n. For the sake of completeness, we also characterize those values of n such that every z ∈ ℤ_{n} can be written as the sum of two squares where the use of zero is allowed as a summand in such a representation of z.

2 Preliminaries and notation

To establish our results, we need some additional facts that follow easily from well-known theorems in number theory. We state these facts without proof. The first proposition follows immediately from the Chinese remainder theorem, while the second proposition is a direct consequence of Hensel’s lemma.

Proposition 11. [3] Suppose that m_{1}, m_{2}, …, m_{t} are integers with m_{i} ≥ 2 for all i, and gcd(m_{i}, m_{j}) = 1 for all i ≠ j. Let c_{1}, c_{2}, …, c_{t} be any integers, and let x ≡ c (mod M) be the solution of the system of congruences x ≡ c_{i} (mod m_{i}) using the Chinese remainder theorem. Then there exists y such that y^{2} ≡ c (mod M) if and only if there exist y_{1}, y_{2}, …, y_{t} such that y_{i}^{2} ≡ c_{i} (mod m_{i}).

Proposition 12. [4] Let p be a prime, and let z be an integer. If there exists x such that x^{2} ≡ z (mod p), then there exists x_{k} such that x_{k}^{2} ≡ z (mod p^{k}) for every integer k ≥ 2.

Throughout this article, we let (\frac{a}{p}) denote the Legendre symbol, where p is a prime and a ∈ ℤ. Using Legendre symbols, the following well-known result can be established.

Proposition 13. [3] Let p ≥ 3 be prime, and let (RR) be the number of pairs (w, w + 1), with w, w + 1 ∈ {1, 2, …, p − 1}, such that both w and w + 1 are quadratic residues modulo p. Then

(RR) = \frac{p − 4 − (−1)^{(p−1)/2}}{4} .

The following useful corollary is an immediate consequence of Proposition 13 and Proposition 12.

Corollary 14. Let p ≥ 7 be prime, and let k ≥ 1. Then there exist w, w+1 ∈ {1, 2, …, p−1}, such that both w and w + 1 are quadratic residues modulo p^{k}.

For an integer n ≥ 2, we define

S_{n} := {s ∈ ℤ | 1 ≤ s < n and s ≡ x^{2} (mod n) for some x ∈ ℤ} ,

and

S_{n}^{0} := S_{n} ∪ {0}.

Then for a given z ∈ ℤ_{n}, a pair (x, y) ∈ ℤ × ℤ such that

x^{2} + y^{2} ≡ z (mod n)  (1)

is called a nontrivial solution to (1), provided x^{2} ≡ a (mod n) and y^{2} ≡ b (mod n) for some a, b ∈ S_{n}. A solution (x, y) to (1), where either x^{2} ≡ 0 (mod n) or y^{2} ≡ 0 (mod n), is called a trivial solution. For the sake of convenience, for any z ∈ ℤ, we abuse notation slightly by writing z ∈ S_{n} (or S_{n}^{0}), if z ≡ s (mod n) for some s ∈ S_{n} (or S_{n}^{0}).

3 Not allowing zero as a summand

In this section we prove the main result in this article, but first we prove a lemma.

Lemma 15. Let z and a ≥ 1 be integers. Let p ≡ 1 mod 4 and q ≡ 3 (mod 4) be primes. Then each of the congruences

x^{2} + y^{2} ≡ z (mod 2)  (2)
x^{2} + y^{2} ≡ z (mod p^{a})  (3)
x^{2} + y^{2} ≡ z (mod q).  (4)

has a solution. Moreover, there exists a nontrivial solution to (3) if either

z ∉ S_{p^{a}} or z ∈ S_{p^{a}} and p ≥ 13.  (5)

Proof. We first point out that if any of the congruences in (2), (3) or (4) has a solution when z ≢ 0 (mod m), where m ∈ {2, p^{a}, q}, we can always choose x (or y) such that x^{2} ≢ 0 (mod m) (or y^{2} ≢ 0 (mod m)). Additionally, we show that such a solution can be chosen when z ≡ 0 (mod m) and m ≠ q.

Clearly, (2) always has a solution for any z, so we address (3). By Proposition 5, there exist positive integers x^{2} and y^{2} such that x^{2} + y^{2} = p^{a}. Then, since neither x^{2} nor y^{2} is divisible by p^{a}, we have a nontrivial solution to (3) when z ≡ 0 (mod p^{a}). So, assume that z ≢ 0 (mod p^{a}), and write z = z′p^{b}, where 0 ≤ b < a and z′ ≢ 0 (mod p). Consider the arithmetic progression

A_{k} := 4p^{a}k + p^{a}(1 − z′) + z′.

Note that for any integer k, we have that A_{k} ≡ z′ (mod p^{a}) and A_{k} ≡ 1 (mod 4). Then, since gcd (4p^{a}, p^{a}(1 − z′) + z′) = 1, it follows from Dirichlet’s theorem on primes in an arithmetic progression that A_{k} contains infinitely many primes r ≡ 1 (mod 4). For such a prime r, Theorem 9 tells us that there exist nonzero integers x^{2} and y^{2} such that x^{2} + y^{2} = p^{b}r. Observe that x^{2} and y^{2} cannot both be divisible by p^{a} since p^{b}r ≡ z ≢ 0 (mod p^{a}). Hence,

(3) always has a solution.

We now show that there exists a nontrivial solution in the special cases of (3) in (5). If z ∉ S_{p^{a}}, we see that neither x^{2} ≡ 0 (mod p^{a}) nor y^{2} ≡ 0 (mod p^{a}) in any solution of (3). Thus, every solution to (3) is nontrivial in this case. Next, suppose that z ∈ S_{p^{a}} and p ≥ 13. Then, by Corollary 14, there exist w, w + 1 ∈ {1, 2, ⋯, p − 1}, such that w, w + 1 ∈ S_{p^{a}}. Since p ≡ 1 (mod 4), we have that −w ∈ S_{p^{a}}. Hence, there exist x and y such that

x^{2} ≡ −w ≢ 0 (mod p^{a}) and y^{2} ≡ w + 1 ≢ 0 (mod p^{a}),

so that (x, y) is a nontrivial solution to x^{2} + y^{2} ≡ 1 (mod p^{a}). Since z ∈ S_{p^{a}}, there exists v such that v^{2} ≡ z (mod p^{a}). Thus, (vx)^{2} + (vy)^{2} ≡ z (mod p^{a}). We claim that (vx, vy) is a nontrivial solution. To see this, suppose that (vy)^{2} ≡ 0 (mod p^{a}). Then,

z ≡ (vx)^{2} ≡ z(−w) (mod p^{a}),

which implies that z(w + 1) ≡ 0 (mod p^{a}). Hence, since w + 1 ≢ 0 (mod p), we have that z ≡ 0 (mod p^{a}), which is a contradiction. A similar argument shows that (vx)^{2} ≢ 0 (mod p^{a}). This completes the analysis of (3).

Finally, we show that (4) always has a solution. If z ≡ 0 (mod q), then we can take x ≡ y ≡ 0 (mod q). If z ≢ 0 (mod q), then we consider the arithmetic progression

B_{k} := 4qk + q(3 + z) + z.

Note here that B_{k} ≡ z (mod q) and B_{k} ≡ 1 (mod 4) for any integer k. As before, since gcd (4q, q(3 + z) + z) = 1, it follows from Dirichlet’s theorem that B_{k} contains infinitely many primes r ≡ 1 (mod 4). Thus, by Proposition 5, there exist nonzero integers x^{2} and y^{2} such that x^{2} + y^{2} = r for such a prime r. Clearly, not both x^{2} and y^{2} are divisible by q, and so we have a desired solution to (4), which completes the proof of the lemma.

Theorem 16. Let n ≥ 2 be an integer. Then, for every z ∈ ℤ_{n}, (1) has a nontrivial solution if and only if all of the following conditions hold:

1. n ≢ 0 (mod q^{2}) for any prime q ≡ 3 (mod 4) with n ≡ 0 (mod q)

2. n ≢ 0 (mod 4)

3. n ≡ 0 (mod p) for some prime p ≡ 1 (mod 4)

4. Also, when n ≡ 1 (mod 2), we have the following additional conditions. Write n = 5^{k}m, where m ≢ 0 (mod 5). Then either

(a) k ≥ 3, with no further restrictions on m, or

(b) k ≤ 2 and m ≡ 0 (mod p) for some prime p ≡ 1 (mod 4).

Proof. Suppose first that, for every z ∈ ℤ_{n}, (1) has a nontrivial solution. Let q be a prime divisor of n. Then there exist a^{2}, b^{2}, c^{2}, d^{2}, e^{2}, f^{2} ∈ S_{n}, such that

a^{2} + b^{2} ≡ q (mod n),  (6)
c^{2} + d^{2} ≡ −1 (mod n) and  (7)
e^{2} + f^{2} ≡ 0 (mod n).  (8)

Suppose that q ≡ 3 (mod 4) is a prime such that n ≡ 0 (mod q^{2}). Then we have from (6) that

a^{2} + b^{2} = kq^{2} + q = q(kq + 1),  (9)

for some nonzero k ∈ ℤ. However, (9) contradicts Theorem 1, since clearly q divides q(kq+1) to an odd power. This proves that 1. holds.

If n ≡ 0 (mod 4), then we have from (7) that c^{2} + d^{2} ≡ 3 (mod 4), which is impossible since the set of all squares modulo 4 is {0, 1}. Hence, 2. holds.

We see from (8) that e^{2} ≡ −f^{2} (mod q) for every prime q ≡ 3 (mod 4) with n ≡ 0 (mod q). Since (\frac{−1}{q}) = −1 for primes q ≡ 3 (mod 4), we deduce that e ≡ f ≡ 0 (mod q). Hence, if n ≡ 1 (mod 2) and n is divisible by no prime p ≡ 1 (mod 4), it follows from (1) that e ≡ f ≡ 0 (mod n), which contradicts the fact that e^{2}, f^{2} ∈ S_{n}. From (2), if n ≡ 0 (mod 2), then we can write n = 2m, where m ≡ 1 (mod 2). By hypothesis, there exist s^{2}, t^{2} ∈ S_{n} such that s^{2} + t^{2} ≡ m (mod n). If m is divisible by no prime p ≡ 1 (mod 4), then as before, since (\frac{−1}{q}) = −1 for primes q ≡ 3 (mod 4), we conclude that s ≡ t ≡ 0 (mod m). But s^{2} + t^{2} ≡ 1 (mod 2) which implies, without loss of generality, that s ≡ 0 (mod 2). Therefore, s ≡ 0 (mod n), which contradicts the fact that s^{2} ∈ S_{n}. Thus, 3. holds.

Assume now that n ≡ 1 (mod 2), and write n = 5^{k}m, where m ≢ 0 (mod 5). Consider first the possibility that k = 1 and no prime p ≡ 1 (mod 4) divides m. To rule this case out, we assume first that (\frac{m}{5}) = 1. By hypothesis, there exist s^{2}, t^{2} ∈ S_{n} such that s^{2} + t^{2} ≡ m (mod n). If m = 1, then n = 5 and this is impossible since the set of nonzero squares modulo 5 is {1, 4}. If m > 1 then every prime divisor q of m is such that q ≡ 3 (mod 4). So, we must have, as before, that s ≡ t ≡ 0 (mod m). Therefore, since s^{2}, t^{2} ∈ S_{n}, we deduce that s^{2} ≢ 0 (mod 5) and t^{2} ≢ 0 (mod 5). Since (\frac{m}{5}) = 1, it follows modulo 5 that s^{2}, t^{2}, m ∈ \{1, 4\}. But then again, s^{2} + t^{2} ≡ m (mod 5) is impossible. If (\frac{m}{5}) = −1, then the proof is identical, except that the representation s^{2} + t^{2} ≡ 2m (mod n) is impossible since modulo 5 we have m ∈ {2, 3}, which implies that s^{2} + t^{2} ≡ 2m (mod 5) is impossible.

The possibility that k = 2 and no prime p ≡ 1 (mod 4) divides m can be ruled out in a similar manner by using the fact that the nonzero squares modulo 25 are {1, 4, 6, 9, 11, 14, 16, 19, 21, 24}, and reducing the situation to an examination of the representations:

s^{2} + t^{2} ≡ \begin{cases}1 (mod 25), & if m = 1; \\ m (mod 25), & if m > 1 and (\frac{m}{5}) = 1; \\ 2m (mod 25), & if m > 1 and (\frac{m}{5}) = −1. \end{cases}

This completes the proof of the theorem in this direction.

Now suppose that conditions 1., 2., 3. and 4. hold, and let z be a nonnegative integer. If n ≠ 5^{k} with k ≥ 3, then we can use Lemma 15 and Proposition 11, if necessary, to piece together the solutions for each distinct prime power dividing n to get a nontrivial solution to (1). Therefore, assume that n = 5^{k} with k ≥ 3. We show that the congruence

x^{2} + y^{2} ≡ z (mod 5^{k}),  (10)

always has a nontrivial solution. Since x^{2} + y^{2} = 5^{k} has a solution (by Theorem 9) with neither x^{2} nor y^{2} divisible by 5^{k}, it follows that (10) has a nontrivial solution when z ≡ 0 (mod 5^{k}). Now suppose that z ≢ 0 (mod 5^{k}). We know from Lemma 15 that (10) has a solution with y^{2} ≢ 0 (mod 5^{k}). If z ∉ S_{5^{k}}, then it must be that x^{2} ≢ 0 (mod 5^{k}) as well, which gives us a nontrivial solution. So, let z ∈ S_{5^{k}}. Since −24 ≡ 1 ∈ S_{5}, it follows from Proposition 12 that, for any integer k ≥ 2, there exists x such that

x^{2} ≡ −24 (mod 5^{k}),  (11)

with x^{2} ≢ 0 (mod 5^{k}). We can rewrite (11) as

x^{2} + 5^{2} ≡ 1 (mod 5^{k}),  (12)

which implies that (3) has a nontrivial solution when z ≡ 1 (mod 5^{k})–provided that k ≥ 3, which we have assumed here. Also, note that this nontrivial solution to (12) has x^{2} ≢ 0 (mod 5). Hence, for any z ∈ S_{5^{k}} with z ≢ 0 (mod 5), we see that multiplying (12) by z yields a nontrivial solution to (3) for these particular values of z. Now suppose that z ∈ S_{5^{k}} with z ≡ 0 (mod 5). Then z − 1 ≡ 4 (mod 5) and, by Proposition 12, we have, for any integer k ≥ 2, that there exists x ≢ 0 (mod 5^{k}) such that x^{2} ≡ z − 1 (mod 5^{k}). That is,

x^{2} + 1 ≡ z (mod 5^{k}),

and hence we have a nontrivial solution to (1) in this last case, which completes the proof of the theorem.

The first 25 values of n satisfying the conditions of Theorem 16 are

10, 13, 17, 26, 29, 30, 34, 37, 39, 41, 50, 51, 53, 58, 61, 65, 70, 73, 74, 78, 82, 85, 87, 89, 91.

This sequence is \underline{A240109} in the Online Encyclopedia of Integer Sequences.

4 Allowing zero as a summand

For the sake of completeness, we address now the situation when trivial solutions are allowed in (1). The main theorem of this section gives a precise description of the integers n such that, for any z ∈ ℤ_{n}, (1) has a solution (x, y) with x^{2}, y^{2} ∈ S_{n}^{0}. Certainly, the proof of this result builds off of Theorem 16 since every value of n for which there exists a nontrivial solution to (1) will be included here as well. From an analysis of the proof of Theorem 16, it is easy to see that allowing 0 as a summand does not buy us any new values of n here under the restrictions found in parts 1. and 2. of Theorem 16. However, it turns out that the restrictions in parts 3. and 4. of Theorem 16 are not required. More precisely, we have:

Theorem 17. Let n be a positive integer. Then, for every z ∈ ℤ_{n}, the congruence (1) has a solution (x, y) with x^{2}, y^{2} ∈ S_{n}^{0} if and only if the following conditions hold:

1. n ≢ 0 (mod q^{2}) for any prime q ≡ 3 (mod 4) with n ≡ 0 (mod q)

2. n ≢ 0 (mod 4).

Proof. It is easily seen that the theorem holds for n = 1. So, assume that n ≥ 2. We show first that condition 3. of Theorem 16 is not required here. Suppose that every prime divisor p of n is such that p ≡ 3 (mod 4). Certainly, if z ∈ ℤ_{n} is such that z ≡ a^{2} (mod n) for some a ∈ ℤ_{n}, then (1) has a solution (x, y), with x^{2}, y^{2} ∈ S_{n}^{0}; namely (a, 0). So, we need to show that (1) has a solution (x, y) with x^{2}, y^{2} ∈ S_{n}^{0} for every nonsquare z ∈ ℤ_{n}. To begin, we claim that (1) has a solution modulo p when z = −1, which is not a square modulo p. For a ∈ ℤ_{p}, if (\frac{a}{p}) = 1 and (\frac{a+1}{p}) = −1, then (\frac{−a−1}{p}) = 1. Thus,

a + (−a − 1) ≡ −1 (mod p).

Such an element a ∈ ℤ_{p} must exist, otherwise all elements of ℤ_{p} would be squares, which is absurd. Now, any nonsquare z ∈ ℤ_{p} can be written as −(−z), where (\frac{−z}{p}) = 1. Therefore,

(\frac{−za}{p}) = (\frac{−z(−a−1)}{p}) = 1, and we have that

(−za) + (−z)(−a − 1) ≡ z (mod p).

Then we can use Proposition 12 to lift this solution modulo p to a solution modulo p^{a}, where p^{a} is the exact power of p that divides n. Finally, we use Proposition 11 to piece together the solutions for each of these prime powers to get a solution modulo n.

To see that the restrictions in part 4. of Theorem 16 are not required here, we note that the restriction that m be divisible by some odd prime p ≡ 1 (mod 4) is not required by the previous argument. Therefore, to complete the proof of the theorem, it is enough to observe that every element in ℤ_{5} and ℤ_{25} can be written as the sum of two elements in S_{5}^{0} and S_{25}^{0}, respectively.

The first 25 values of n satisfying the conditions of Theorem 17 are

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 30, 31, 33, 34, 35, 37.

This sequence is \underline{A240370} in the Online Encyclopedia of Integer Sequences.

5 Future considerations

Theorem 16 and Theorem 17 consider the situation when the entire ring ℤ_{n} can be obtained as the sum of two squares. When this cannot be attained, how badly does it fail; and is there a measure of this failure in terms of n? There are certain clues to the answers to these questions in the proof of Theorem 16, but we have not pursued the solution in this article.

6 Acknowledgments

The authors thank the referee for suggestions that improved the paper.

References

[1] B. Fine, Sum of squares rings, Canad. J. Math 29 (1977), 155–160.

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth edition, Oxford University Press, 1979.

[3] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1990.

[4] M. Nathanson, Elementary Methods in Number Theory, Springer-Verlag, 2000.

[5] J. Suzuki, Euler and Number Theory: A Study in Mathematical Invention, Leonhard Euler: Life, Work and Legacy, Studies in the History of Philosophy of Mathematics, 5, Robert E. Bradley and C. Edward Sandifer, eds., Elsevier, 2007.

[6] H. Wegmann, Quadratsummen in Restklassenringen. Elem. Math. 38 (1983), 36–39.

2010 Mathematics Subject Classification: Primary 11E25; Secondary 11A07. Keywords: sums of squares, ring of integers modulo n, congruence.

(Concerned with sequences \underline{A240109}, \underline{A240370}, and \underline{A243609}.)

Received April 1 2014; revised versions received June 10 2014; June 12 2014. Published in Journal of Integer Sequences, June 21 2014. Minor revision, July 1 2014. Major revision, March 26 2015.

Return to Journal of Integer Sequences home page.