Special Numbers in the Ring ℤ_{n}

Joshua Harrington Department of Mathematics Cedar Crest College Allentown, PA 18104 USA

                 Joshua.Harrington@cedarcrest.edu

Samuel S. Gross Noblis, Inc. Falls Church, VA 22042 USA

                   samuel.gross@noblis-nsp.com

Abstract

In a recent article, Nowicki introduced the concept of a special number. Specifically, an integer d is called special if for every integer m there exist solutions in non-zero integers a, b, c to the equation a^{2} + b^{2} − dc^{2} = m. In this article we investigate pairs of integers (n, d), with n ≥ 2, such that for every integer m there exist units a, b, and c in ℤ_{n} satisfying m ≡ a^{2} + b^{2} − dc^{2} (mod n). By refining a recent result of Harrington, Jones, and Lamarche on representing integers as the sum of two non-zero squares in ℤ_{n}, we establish a complete characterization of all such pairs.

1 Introduction

The following definition was recently stated by Nowicki [4].

Definition 1. We call a positive integer d special if for every integer m there exist non-zero integers a, b, and c so that a^{2} + b^{2} − dc^{2} = m.

The necessary conditions of the following theorem were proven by Nowicki, while Lam [3] later provided the sufficient conditions.

Theorem 2. An integer d is special if and only if d is of the form q or 2q where either q = 1 or q is a product of primes all congruent to 1 modulo 4.

With this complete representation of special numbers, the following theorem follows from Dirichlet’s theorem on primes in arithmetic progression (see Theorem 8 below) and the Chinese remainder theorem. For completeness, we provide a proof of this theorem in Section 4.

Theorem 3. For any odd integer n ≥ 3, any d with gcd(d, n) = 1, and any integer m, there exist integers a, b, and c such that a^{2} + b^{2} − dc^{2} ≡ m (mod n).

In light of Theorem 3, we give the following definition, which imposes a unit restriction on a, b, and c.

Definition 4. We say that d is unit-special in ℤ_{n} if for an integer m, there exist units a, b, and c in ℤ_{n} with a^{2} + b^{2} − dc^{2} ≡ m (mod n).

We note that the requirement that a, b, and c be units in ℤ_{n} ensures that a^{2}, b^{2}, and c^{2} are non-zero in ℤ_{n}. Although one could loosen this restriction to just require a^{2}, b^{2}, and c^{2} to be non-zero, this is not the setting that we investigate in this article. Among the results in this article, we provide the following complete characterization of unit-special numbers in ℤ_{n}.

Theorem 5. Let n be a positive integer. An integer d is unit-special in ℤ_{n} if and only if the following three conditions hold:

• n is not divisible by 2 or 3.

• If p ≡ 3 (mod 4) is prime and p divides n, then gcd(d, p) = 1.

• If 5 divides n, then d ≡ ±2 (mod 5).

To establish Theorem 5 we first refine a recent result of Harrington, Jones, and Lamarche [2] on representing integers as the sum of two non-zero squares in the ring ℤ_{n}, stated below.

Theorem 6. Let n ≥ 2 be an integer. The equation

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

has a non-trivial solution (x^{2}, y^{2} ≢ 0 (mod n)) for all z in ℤ_{n} if and only if all of the following are true.

1. q^{2} does not divide n for any prime q ≡ 3 (mod 4).

2. 4 does not divide n.

3. n is divisible by some prime p ≡ 1 (mod 4).

4. If n is odd and n = 5^{k}m with gcd(5, m) = 1 and k < 3, then m is divisible by some prime p ≡ 1 (mod 4).

At the end of their article, Harrington, Jones, and Lamarche ask the following question.

Question 1. Theorem 6 considers the situation when the entire ring ℤ_{n} can be obtained as the sum of two non-zero squares. When this cannot be attained, how badly does it fail?

In this article, we address Question 1 in a slightly refined setting. In particular, we prove the following theorem.

Theorem 7. Let n ≥ 2 be an integer. For a fixed integer z, there exist units a and b in ℤ_{n} such that a^{2} + b^{2} ≡ z (mod n) if and only if all of the following hold:

• If p ≡ 3 (mod 4) is a prime dividing n, then gcd(z, p) = 1.

• If 5 divides n, then z ≢ ±1 (mod 5).

• If 3 divides n, then z ≡ 2 (mod 3).

• If 2 divides n and 4 does not, then z ≡ 0 (mod 2).

• If 4 divides n and 8 does not, then z ≡ 2 (mod 4).

• If 8 divides n, then z ≡ 2 (mod 8).

We again note that the requirement that a and b are units in ℤ_{n} ensures that a^{2} and b^{2} are non-zero in ℤ_{n}. Since Question 1 does not have the unit restriction, Theorem 7 does not give a complete answer to the question. However, it does provide sufficient conditions in the setting of Question 1. Although the majority of this article focuses on the refined setting where a and b are units in ℤ_{n}, we do briefly investigate the more general setting of Question 1 and provide a result in this direction.

2 Preliminaries and notation

We will make use of the following results and definitions from classical number theory (see, for example [1]).

Theorem 8 (Dirichlet). Let a, b be integers such that gcd(a, b) = 1. Then the sequence {ak + b}, over integers k, contains infinitely many primes.

Definition 9. Let p be an odd prime. The Legendre symbol of an integer a modulo p is given by

(\frac{a}{p}) = \begin{cases}1, & if a is a non-zero square modulo p; \\ −1, & if a is not a square modulo p; \\ 0, & if a ≡ 0 (mod p). \end{cases}

Theorem 10. Let p ≥ 7 be a prime. There exist non-zero elements t, u, v, and w in ℤ_{p} such that

\begin{aligned}(\frac{u}{p}) & = & (\frac{u+1}{p}) = 1, & (\frac{v}{p}) & = & (\frac{v+1}{p}) = −1, \\ (\frac{w}{p}) & = & − (\frac{w+1}{p}) = 1, and & (\frac{t}{p}) & = & − (\frac{t+1}{p}) = −1. \end{aligned}

The following result can be found in a book of Suzuki’s [5] and is originally due to Euler.

Theorem 11. 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.

The following theorem, which follows immediately from the Chinese remainder theorem, appears in Harrington, Jones, and Lamarche’s article.

Theorem 12. Suppose that m_{1}, m_{2}, …, m_{t} are all pairwise relatively prime integers ≥ 2, and set M = m_{1}m_{2} ⋯ m_{k}. 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 a 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}).

3 Sums of squares in ℤ_{n}

We begin by examining when integers are a sum of two unit squares modulo n. Later we shall relax this condition and only require both squares to be non-zero modulo n.

Let us first examine the case when the modulus is a power of 2.

Theorem 13. Let k be a positive integer. For a fixed integer z, there exist units a and b in ℤ_{2^{k}} such that a^{2} + b^{2} ≡ z (mod 2^{k}) if and only if one of the following is true:

• k = 1 and z ≡ 0 (mod 2);

• k = 2 and z ≡ 2 (mod 4);

• k ≥ 3 and z ≡ 2 (mod 8).

Proof. We computationally check that the theorem is true for k ≤ 3.

Suppose k > 3. If a^{2} + b^{2} ≡ z (mod 2^{k}), then a^{2} + b^{2} ≡ z (mod 8). Thus, we deduce that z ≡ 2 (mod 8).

Conversely, suppose that z ≡ 2 (mod 8). We proceed with a proof by induction on k. We have already established the base case k ≤ 3. Suppose that the theorem holds for k − 1 so that that there are units a and b in ℤ_{2^{k−1}} such that a^{2} + b^{2} ≡ z (mod 2^{k−1}). Then for some odd integer t and some integer r ≥ k − 1 we can write

a^{2} + b^{2} = z + t2^{r}.

If r ≥ k, then a^{2} + b^{2} ≡ z (mod 2^{k}), as desired. So suppose that r = k − 1. Then

a^{2} + (b + 2^{k−2})^{2} = a^{2} + b^{2} + b2^{k−1} + 2^{2k−4}
= z + t2^{k−1} + b2^{k−1} + 2^{2k−4}
= z + 2^{k−1}(t + b) + 2^{2k−4}.

Since k ≥ 4, we know that 2^{2k−4} ≡ 0 (mod 2^{k}). Also, since b was chosen to be a unit in ℤ_{2^{k−1}}, then b must be odd. Thus, t + b is even and we deduce that 2^{k−1}(t + b) ≡ 0 (mod 2^{k}). Hence,

a^{2} + (b + 2^{k−2})^{2} ≡ z (mod 2^{k}).

It follows that b + 2^{k−2} is an odd integer and is therefore a unit in ℤ_{2^{k}}, as desired.

We next treat the case where the modulus is a power of an odd prime. The following is an application of Hensel’s Lifting Lemma. We provide the proof here for completeness.

Lemma 14. For an odd prime p and integer z, suppose there are non-zero elements a and b_{1} in ℤ_{p} such that a^{2} + b_{1}^{2} ≡ z (mod p). Then for any positive integer k, the integer a is a unit in ℤ_{p^{k}} and there exists a unit b_{k} in ℤ_{p^{k}} such that a^{2} + b_{k}^{2} ≡ z (mod p^{k}).

Proof. Suppose that a^{2} + b_{1}^{2} ≡ z (mod p) for some non-zero elements a and b_{1} in ℤ_{p}. Then for some integer t_{1}, a^{2} + b_{1}^{2} = z + t_{1}p. Let b_{2} ≡ b_{1} − t_{1}p(2b_{1})^{−1} (mod p^{2}), and note that b_{2} is a unit in ℤ_{p^{2}}. It follows that

a^{2} + b_{2}^{2} ≡ a^{2} + (b_{1} − t_{1}p(2b_{1})^{−1})^{2} (mod p^{2})
≡ a^{2} + b_{1}^{2} − t_{1}p (mod p^{2})
≡ z + t_{1}p − t_{1}p (mod p^{2})
≡ z (mod p^{2}).

Since a is also a unit modulo p^{2}, this proves the result for k = 2. The remainder of the theorem now follows by induction on k with

a^{2} + b_{k+1}^{2} ≡ z (mod p^{k+1}),

where b_{k+1} ≡ b_{k} − t_{k}p^{k}(2b_{k})^{−1} (mod p^{k}) with t_{k} satisfying a^{2} + b_{k}^{2} = z + t_{k}p^{k}.

An appropriate converse for Lemma 14 can be stated, however the information contained in such a statement varies with the modulus. Specifically, we can easily prove the following two theorems after verifying the base case k = 1 and applying Lemma 14.

Theorem 15. Let k be a positive integer. For a fixed integer z, there exist units a and b in ℤ_{3^{k}} with a^{2} + b^{2} ≡ z (mod 3^{k}) if and only if z ≡ 2 (mod 3).

Theorem 16. Let k be a positive integer. For a fixed integer z, there exist units a and b in ℤ_{5^{k}} with a^{2} + b^{2} ≡ z (mod 5^{k}) if and only if z ≢ ±1 (mod 5).

For powers of primes that are 1 modulo 4, we have the following theorem which is a bit more general then Lemma 14.

Theorem 17. Let p ≥ 13 be a prime with p ≡ 1 (mod 4) and let k be a positive integer. For every integer z, there exist units a and b in ℤ_{p^{k}} such that a^{2} + b^{2} ≡ z (mod p^{k}).

Proof. We show that the result holds for k = 1 and the remainder of the proof will follow from Lemma 14. So let k = 1. First suppose that z ≡ 0 (mod p). Since p ≡ 1 (mod 4), we know that −1 is a square modulo p. Thus, we can let

a^{2} ≡ 1 (mod p)  and  b^{2} ≡ p − 1 (mod p)

so that a^{2} + b^{2} ≡ z (mod p), where a and b are units modulo p.

Now suppose that z ≢ 0 (mod p). Since p ≥ 7, we can use Theorem 10 to choose u such that

(\frac{u}{p}) = (\frac{u − 1}{p}) = (\frac{z}{p}) .

It follows that

(\frac{uz}{p} ) = (\frac{−(u − 1)z}{p} ) = 1.

Thus, letting

a^{2} ≡ uz (mod p)  and  b^{2} ≡ −(u − 1)z (mod p)

proves the result for k = 1 since u, u − 1, and z are all units modulo p.

In the next corollary, which provides an extension of Theorem 6 to our new unit-setting, we piece together the information in Theorem 17 using the Chinese remainder theorem as stated in Theorem 12.

Corollary 18. Let n ≥ 13 be an odd integer not divisible by 5 and with all prime divisors congruent to 1 modulo 4. Then for any fixed integer z, there exist units a and b in ℤ_{n} with a^{2} + b^{2} ≡ z (mod n).

We now turn our attention to primes that are 3 modulo 4.

Theorem 19. Let p ≥ 7 be a prime with p ≡ 3 (mod 4) and let k be a positive integer. For a fixed integer z, there exist units a and b in ℤ_{p^{k}} with a^{2} + b^{2} ≡ z (mod p^{k}) if and only if z is a unit in ℤ_{p^{k}}.

Proof. First suppose that the a and b are units modulo p^{k} with a^{2} + b^{2} ≡ z (mod p^{k}). If z is not a unit modulo p^{k}, then z ≡ xp (mod p^{k}) for some integer x, whence z ≡ 0 (mod p). It follows that a^{2} ≡ −b^{2} (mod p). However, this leads to a contradiction since

(\frac{−b^{2}}{p} ) = (\frac{−1}{p}) · (\frac{b^{2}}{p} ) = −1.

For the converse, we show that the result holds for k = 1 and the remainder of the proof will follow from Lemma 14. In this case, choose u from Theorem 10 such that

(\frac{u}{p}) = − (\frac{u − 1}{p}) = (\frac{z}{p}) .

It follows that

(\frac{uz}{p} ) = (\frac{−(u − 1)z}{p} ) = 1.

Thus, letting

a^{2} ≡ uz (mod p)  and  b^{2} ≡ −(u − 1)z (mod p)

proves the result for k = 1 since u, u − 1, and z are all units modulo p.

Piecing together Theorems 13,15,16,17, and 19 using the Chinese remainder theorem as stated in Theorem 12 provides a proof for Theorem 7. We note once more that Theorem 7 provides some insight in to Question 1.

The following two corollaries are immediate consequences of Theorem 7.

Corollary 20. Suppose n is odd and not divisible by 3 or 5. If z is a unit modulo n, then there exist units a and b in ℤ_{n} such that a^{2} + b^{2} ≡ z (mod n).

Corollary 21. If n is even, then no unit can be written as the sum of two square units.

To further address Question 1, in the following theorem we loosen the restriction that a and b are units in ℤ_{p^{k}} and instead only require a^{2} and b^{2} to be non-zero modulo p^{k}.

Theorem 22. Let p ≥ 7 be a prime with p ≡ 3 (mod 4) and let k be a positive integer. For a fixed non-zero element z ∈ ℤ_{p^{k}}, there exist elements a and b with a^{2} and b^{2} each non-zero in ℤ_{p^{k}} such that a^{2} + b^{2} ≡ z (mod p^{k}) if and only if z ≡ xp^{r} (mod p^{k}) for some unit x in ℤ_{p^{k}} and some non-negative even integer r < k.

Proof. Suppose that a^{2} and b^{2} are non-zero elements in ℤ_{p^{k}} with a^{2} + b^{2} ≡ z (mod p^{k}). If z is a unit in ℤ_{p^{k}}, then we may write z ≡ zp^{0} (mod p^{k}) which proves the result. Suppose, then, that z is not a unit in ℤ_{p^{k}}. Since z ≢ 0 (mod p^{k}), then we can write z ≡ xp^{r} (mod p^{k}) for some unit x ∈ ℤ_{p^{k}} and some positive integer r < k. Thus,

a^{2} + b^{2} = xp^{r} + cp^{k} = p^{r}(x + cp^{k−r}),

for some c ∈ ℤ. It follows that p divides a^{2} + b^{2}, but p does not divide x + cp^{k−r} since x is a unit in ℤ_{p^{k}}. Hence, p^{r} divides a^{2} + b^{2}, but p^{r+1} does not. Since p ≡ 3 (mod 4), it follows by Theorem 11 that r must be even.

Conversely, suppose that z ≡ xp^{r} (mod p^{k}) for some unit x ∈ ℤ_{p^{k}} and some non-negative even integer r < k. Since x is a unit in ℤ_{p^{k}}, it follows by Theorem 19 that there exist units u and v such that u^{2} + v^{2} ≡ x (mod p^{k}). Since r is an even integer, we may define a ≡ up^{r/2} (mod p^{k}) and b ≡ vp^{r/2} (mod p^{k}). Notice that a^{2} and b^{2} are non-zero in ℤ_{p^{k}} since r < k. Furthermore,

a^{2} + b^{2} ≡ (up^{r/2})^{2} + (vp^{r/2})^{2} (mod p^{k})
≡ u^{2}p^{r} + v^{2}p^{r} (mod p^{k})
≡ xp^{r} (mod p^{k}).

This completes the proof of the theorem.

The Chinese remainder theorem as stated in Theorem 12 along with Theorems 6 and 22 partially answers Question 1 when n is not divisible by 2 or 3.

4 Special numbers in ℤ_{n}

For convenience and completeness, we restate and prove Theorem 3.

Theorem. For any odd integer n ≥ 3, any unit d in ℤ_{n}, and any integer m, there exist integers a, b, and c such that a^{2} + b^{2} − dc^{2} ≡ m (mod n).

Proof. Let n ≥ 3 be an integer and let d be a unit in ℤ_{n}. By the Chinese remainder theorem and Theorem 8 there exists some prime p satisfying

p ≡ 1 (mod 4)  and  p ≡ d (mod n).

It follows from Theorem 2 that such a prime must be a special number. Therefore, for any integer m, there exist integers a, b, and c such that a^{2} + b^{2} − pc^{2} = m. In this case a, b, and c will satisfy

a^{2} + b^{2} − dc^{2} ≡ m (mod n).

This proves the theorem.

Our main goal in this section is to prove Theorem 5. To do this, we first establish three lemmas.

Lemma 23. Let k be a positive integer. Then there are no unit-special numbers modulo 2^{k} or 3^{k}.

Proof. The theorem can be checked computationally for k = 1. Let p ∈ {2, 3} and k > 1. Suppose that d is unit-special in ℤ_{p^{k}}. Then there exist units a, b, and c in ℤ_{p^{k}} such that a^{2}+b^{2}−dc^{2} ≡ z (mod p^{k}) for all z ∈ ℤ_{p^{k}}. It follows that a^{2}+b^{2}−dc^{2} ≡ z (mod p). However, since d is not unit-special in ℤ_{p}, there is some element z ∈ ℤ_{p} that cannot be written in this form. Therefore d cannot be unit-special in ℤ_{p^{k}}.

Lemma 24. Let k be a positive integer. An integer d is unit-special in ℤ_{5^{k}} if and only if d ≡ ±2 (mod 5).

Proof. The theorem can be verified computationally for k = 1. If d is unit-special in ℤ_{5^{k}} for some k > 1, then d is also unit-special modulo 5 whence d ≡ ±2 (mod 5).

Conversely, suppose that k > 1 and d ≡ ±2 (mod 5). Let m be any fixed integer. Then there exist units a, b, and c modulo 5 such that a^{2} + b^{2} − dc^{2} ≡ m (mod 5). As such, by Lemma 14 there exists a unit b_{k} ∈ ℤ_{5^{k}} with

a^{2} + b_{k}^{2} ≡ m + dc^{2} (mod 5^{k}).

Therefore the result holds for all positive integers k.

Lemma 25. For an odd positive integer n not divisible by 3 or 5, if d is a unit in ℤ_{n}, then d is unit-special in ℤ_{n}.

Proof. Let d be a unit modulo n, and fix m ∈ ℤ_{n}. We proceed with two cases as to whether or not m + d is a unit modulo n.

Suppose m + d is a unit modulo n, then by Corollary 20 we may obtain units a and b modulo n such that

a^{2} + b^{2} ≡ m + d (mod n).

The result follows by choosing c ≡ 1 (mod n).

Now suppose that m + d is not a unit modulo n. Factor n as

n = (∏_{i=1}^{t} p_{i}^{e_{i}}) · (∏_{j=1}^{r} q_{j}^{f_{j}})

where each p_{i} is distinct with m + d ≢ 0 (mod p_{i}), and each q_{j} is distinct with m + d ≡ 0 (mod q_{j}). Then it follows from Corollary 20 that there exist units a_{i} and b_{i} in ℤ_{p^{e_{i}}} such that a_{i}^{2} + b_{i}^{2} ≡ m + d (mod p_{i}). Now, notice that since d is a unit modulo n, then d is also a unit modulo q_{j}. We deduce that m + 4d ≢ 0 (mod q_{j}), since otherwise

m + d ≡ 0 (mod q_{j}) ≡ m + 4d (mod q_{j})

would imply that 4 ≡ 1 (mod q_{j}). This cannot happen since n is not divisible by 3. Thus, m + 4d is a unit in ℤ_{q_{j}}. It follows from Corollary 20 that there exist units a′_{i} and b′_{i} in ℤ_{q_{j}^{f_{j}}}

such that

(a′_{i})^{2} + (b′_{i})^{2} ≡ m + 4d (mod q_{j}^{f_{j}}).

Next, we use the Chinese remainder theorem to choose a, b, and c which satisfy the system of congruences

a ≡ a_{i} (mod p_{i}^{e_{i}}) a ≡ a′_{i} (mod q_{j}^{f_{j}})
b ≡ b_{i} (mod p_{i}^{e_{i}}) b ≡ b′_{i} (mod q_{j}^{f_{j}})

and

c ≡ 1 (mod p_{i}^{e_{i}}) c ≡ 2 (mod q_{j}^{f_{j}}).

This ensures that a, b, and c are units in ℤ_{n} with a^{2} + b^{2} − dc^{2} ≡ m (mod n).

The following Corollary follows from Lemma 25 and Theorem 3.

Corollary 26. Let n be an odd positive integer with n ∉ {1, 3, 5, 9, 25}. Then every integer can be written as the sum of three non-zero squares in ℤ_{n}.

Proof. Write n = 3^{r}5^{t}m with m relatively prime to 3 and 5. First suppose that m ≠ 1. Since −1 is a unit in ℤ_{m}, it follows from Lemma 25 that for any integer z there exist units a_{1}, b_{1}, and c_{1} in ℤ_{m} such that a_{1}^{2} + b_{1}^{2} + c_{1}^{2} ≡ z (mod m). Theorem 3 implies that there exist integers a_{2}, b_{2}, and c_{2} such that a_{2}^{2} + b_{2}^{2} + c_{2}^{2} ≡ z (mod 3^{r}5^{t}). Using the Chinese remainder theorem as stated in Theorem 12, there exist a, b, and c such that a^{2} + b^{2} + c^{2} ≡ z (mod n). Such a choice of a ensures that a^{2} ≡ a_{1}^{2} (mod m). Since a_{1} is relatively prime to m we see that m does not divide a^{2}. Thus, n does not divide a^{2}. This shows that a^{2} is non-zero in ℤ_{n}. Similar arguments show that b^{2} and c^{2} are non-zero in ℤ_{n}.

Now suppose that m = 1 so that n = 3^{r}5^{t}. Following the Hensel Lifting argument of Lemma 14, it is easy to show that for a positive integer k, if z can be written as the sum of three non-zero squares in ℤ_{3^{k−1}}, then it can also be written as the sum of three non-zero squares in ℤ_{3^{k}}. We check computationally that every integer can be written as the sum of three non-zero squares in ℤ_{3^{3}}. Thus, for k ≥ 3, we can write every integer as the sum of three non-zero squares in ℤ_{3^{k}}. The same argument shows that we can also write every integer as the sum of three non-zero squares in ℤ_{5^{3}}. Using an argument similar to the one in the first paragraph of the proof, it then follows that if r ≥ 3 or t ≥ 3, every integer can be written as the sum of three non-zero squares in ℤ_{n}. The remaining finite number of cases can easily be confirmed computationally.

We are now in a position to prove Theorem 5.

Proof of Theorem 5. Lemma 23 implies that if d is unit-special in ℤ_{n}, then n is not divisible by 2 or 3. It follows from Lemma 24 that if 5 divides n, then d ≡ ±2 (mod 5). Now suppose that n is divisible by some prime p ≡ 3 (mod 4). If d is unit-special in ℤ_{n}, then we may obtain units a, b, c modulo n such that

a^{2} + b^{2} − dc^{2} ≡ 0 (mod n).

It would then follow that

a^{2} + b^{2} − dc^{2} ≡ 0 (mod p).

If d ≡ 0 (mod p), then this would contradict Theorem 19. As such, we conclude gcd(d, p) = 1.

To prove the converse, we first show that if n is odd, 5 does not divide n, and n is not divisible by any prime p ≡ 3 (mod 4), then every integer is unit-special in ℤ_{n}. To see this, let m and d be fixed integers. By Corollary 18, there exist units a and b in ℤ_{n} such that a^{2} + b^{2} ≡ m + d (mod n). Since m is chosen arbitrarily, this shows that d is unit-special in ℤ_{n} since

a^{2} + b^{2} − d · (1)^{2} ≡ m (mod n).

This observation together with Theorem 12, Lemma 24, and Lemma 25 finishes the proof of the theorem.

5 Acknowledgments

The authors would like to thank the anonymous referee for suggestions that improved this article.

References

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

[2] J. Harrington, L. Jones, and A. Lamarche, Representing integers as the sum of two squares in the ring ℤ_{n}, J. Integer Seq. 17 (2014), Article 14.7.4.

[3] P. C. Lam, Representation of integers Using a^{2} + b^{2} − dc^{2}, J. Integer Seq. 18 (2015), Article 15.8.6.

[4] A. Nowicki, The numbers a^{2} + b^{2} − dc^{2}, J. Integer Seq. 18 (2015), Article 15.2.3.

[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.

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

Received August 1 2015; revised versions received September 18 2015; September 30 2015. Published in Journal of Integer Sequences, November 25 2015.

Return to Journal of Integer Sequences home page.