Counting Integers Representable as Images of Polynomials Modulo n

Fabián Arias Facultad de Ciencias Básicas Universidad Tecnológica de Bolívar Colombia

                   farias@utb.edu.co

Jerson Borja and Luis Rubio Departamento de Matemáticas y Estadística Universidad de Córdoba Colombia

         jersonborjas@correo.unicordoba.edu.co
        lrubiohernandez@correo.unicordoba.edu.co

Abstract

Given a polynomial f(x_{1}, x_{2}, …, x_{t}) in t variables with integer coefficients and a positive integer n, let α(n) be the number of integers 0 ≤ a < n such that the polynomial congruence f(x_{1}, x_{2}, …, x_{t}) ≡ a (mod n) is solvable. We describe a method that allows us to determine the function α associated with polynomials of the form c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}. Then, we apply this method to polynomials that involve sums and differences of squares, mainly to the polynomials x^{2} +y^{2}, x^{2} −y^{2}, and x^{2} +y^{2} +z^{2}.

1 Introduction

For a polynomial f(x_{1}, x_{2}, …, x_{t}) in t variables with integer coefficients, consider the polynomial congruence

f(x_{1}, x_{2}, …, x_{t}) ≡ a (mod n)  (1)

where n is a positive integer and a is an integer. Since the congruence (1) has solution for a if and only if it has solution for a + qn for any integer q, we can assume that a belongs to a complete residue system modulo n. We will use the system of residues I_{n} = {0, 1, , …, n−1}.

For any positive integer n, we set A_{n} to be the set of all a ∈ I_{n} for which (1) has solution. We define α(n) = |A_{n}|, where |A_{n}| stands for the size of A_{n}. The following natural questions about the sets A_{n} and their sizes α(n) guide our work:

1. Give explicit descriptions of A_{n} for all n.

2. Find a formula for α(n).

3. Determine or describe all the values of n such that α(n) = n. This is equivalent to determine if the polynomial f(x_{1}, x_{2}, …, x_{t}) is surjective when it is considered as a map f : ℤ_{n}^{t} → ℤ_{n}. When this map is surjective, we will say that f(x_{1}, x_{2}, …, x_{t}) is surjective on n.

Some results related to these questions with respect to the polynomials x^{2}+y^{2} and x^{3}+y^{3} are found in [2, 3, 4].

Harrington, Jones, and Lamarche [4] solved the problem of characterizing all positive integers n such that every element in the ring ℤ_{n} can be represented as the sum of two squares in ℤ_{n}, or, in our terms, that x^{2} + y^{2} is surjective on n. Such integers n are those satisfying the following two conditions:

(i) n ≢ 0 (mod 4) and

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

They also solved the problem of finding all positive integers n such that every element in ℤ_{n} is expressible as a sum of two squares without allowing zero as a summand. We are interested in the case where zero is allowed as a summand because in that case the sizes α(n) define a multiplicative function.

Burns [3] considered the general problem of representing elements of ℤ_{n} as the sum of two squares. He determined the sizes of the sets A_{p^{n}} associated with x^{2} + y^{2} as follows: First, he gave explicit descriptions of the sets A_{p^{n}}, and then, found the size of A_{p^{n}}, that is, α(n). One key property Burns uses is that the numbers α(n) define a multiplicative function, which implies that for finding α(n) for all positive integers n, it suffices to find α(p^{n}) where p is prime and n ≥ 1.

Explicit formulas for the numbers α(n) associated with the polynomial x^{3}+y^{3} were found by Broughan [2]. Broughan considered the fraction δ(n) = α(n)/n instead of α(n). There is no explicit description of the sets A_{p^{n}} associated with x^{3} + y^{3}, but some properties of δ(n) give, essentially, recursive formulas for finding δ(p^{n}). Again, as in [3], the associated function α is multiplicative.

For a general polynomial f(x_{1}, x_{2}, …, x_{t}), if every nonnegative integer is of the form f(x_{1}, x_{2}, …, x_{t}), then α(n) = n for every n ≥ 1. This is the case for some polynomials as x^{2} + y^{2} + z^{2} + w^{2} or x^{2} + y^{2} − z^{2}. There are theorems that characterize all nonnegative integers that are of the form f(x_{1}, x_{2}, …, x_{t}), for a given polynomial f(x_{1}, x_{2}, …, x_{t}). Three well known theorems that are important for us are the following.

Theorem 1. (Euler) A positive integer n is expressible as a sum of two squares if and only if each prime of the form 4k + 3 appears to an even exponent in the prime decomposition of n.

Theorem 2. (Gauss-Legendre) A nonnegative integer is the sum of three squares if and only if it is not of the form 4^{a}(8b + 7).

Theorem 3. (Lagrange) Every nonnegative integer is expressible as the sum of four squares.

A consequence of Lagrange’s theorem is that for t ≥ 4, the polynomial x_{1}^{2} +x_{2}^{2} +⋯+x_{t}^{2} is surjective on n for all n ≥ 1. Thus, concerning sums of squares, we are interested in finding formulas for α(n) and descriptions of the sets A_{n} associated with the polynomials x^{2} + y^{2} and x^{2} + y^{2} + z^{2}.

We prove that for a general polynomial f(x_{1}, x_{2}, …, x_{t}), the sizes α(n) define a multiplicative function. Therefore, for determining α(n) for all n, it suffices to determine α(p^{n}) for any prime number p and n ≥ 1. This makes us focus on studying the sets A_{p^{n}}, where p is a prime number and n ≥ 1.

In the case of polynomials of the form c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}, we prove some structural results that will permit us to find recurrence formulas for α(p^{n}), for a given prime p and n ≥ 1. Then, we apply these results to find explicit formulas for α(p^{n}), where α is the function associated with one of the polynomials x^{2} + y^{2}, x^{2} − y^{2}, and x^{2} + y^{2} + z^{2}. With this method, we deduce some of the results related to x^{2} + y^{2} proved in [3].

The polynomials x^{2} − y^{2} and x^{2} + y^{2} + z^{2} share the following property: if n = 2^{s}m where s ≥ 0 and m is odd, then α(n) = α(2^{s})m.

In the case of x^{2} −y^{2}, we show that α(2) = 2 and α(2^{s}) = 3·2^{s−2} for s ≥ 2. In particular, x^{2} − y^{2} is surjective on n if and only if n ≢ 0 (mod 4).

For the polynomial x^{2} + y^{2} + z^{2}, we find the explicit formula

α(2^{s}) = \begin{cases}\frac{1}{3}(5 · 2^{s−1} + 1), & if s is odd; \\ \frac{2}{3}(5 · 2^{s−2} + 1), & if s is even. \end{cases}

It follows, from this formula, that x^{2} + y^{2} + z^{2} is surjective on n if and only if n ≢ 0 (mod 8).

2 The multiplicative family associated with a polynomial

For an arbitrary family of nonempty sets {A_{n}}_{n∈ℤ^{+}}, where A_{n} ⊆ I_{n} for all n, we define the function α : ℤ^{+} → ℤ^{+} associated with {A_{n}}_{n} by α(n) = |A_{n}| for all n. Note that α(1) = 1. The first thing we do is to define suitable conditions on the family {A_{n}}_{n} so that the associated function α is multiplicative.

2.1 Multiplicative families and polynomials

If n and m are integers such that 1 ≤ m ≤ n, we define

A_{n}(m) := {s ∈ I_{n} : s ≡ a (mod m) for some a ∈ A_{m}}
= {a + jm : a ∈ A_{m}, 0 ≤ j < n/m}.

We call a family {A_{n}}_{n} multiplicative, if whenever n = m_{1}m_{2} with m_{1} and m_{2} relatively prime, the equality A_{n} = A_{n}(m_{1})∩A_{n}(m_{2}) holds. This condition on the family of sets {A_{n}}_{n} guaranties that the associated function α is multiplicative.

Lemma 4. If {A_{n}}_{n} is a multiplicative family, then the associated function α is multiplicative.

Proof. Let n = m_{1}m_{2} where m_{1} and m_{2} are relatively prime. We decompose A_{n}(m_{1}) as the disjoint union of subsets B(a, m_{1}) := {a + jm_{1} : 0 ≤ j < m_{2}}, where a ∈ A_{m_{1}}. Similarly, A_{n}(m_{2}) is the disjoint union of subsets B(b, m_{2}) = {b + jm_{2} : 0 ≤ j < m_{1}}, where b ∈ A_{m_{2}}. Then,

A_{n}(m_{1}) ∩ A_{n}(m_{2}) = ⋃_{a∈A_{m_{1}},b∈A_{m_{2}}}(B(a, m_{1}) ∩ B(b, m_{2})).

Note that c ∈ B(a, m_{1}) ∩ B(b, m_{2}) if and only if c ≡ a (mod m_{1}) and c ≡ b (mod m_{2}); moreover, by the Chinese remainder theorem, there is exactly one solution in I_{n} of the system of congruences x ≡ a (mod m_{1}), x ≡ b (mod m_{2}). This means that B(a, m_{1}) ∩ B(b, m_{2}) has exactly one element. Since the sets B(a, m_{1}) ∩ B(b, m_{2}), for a ∈ A_{m_{1}}, b ∈ A_{m_{2}}, are pairwise disjoint, we have |A_{n}(m_{1}) ∩ A_{n}(m_{2})| = |A_{m_{1}}| · |A_{m_{2}}|. Now, if the family {A_{n}}_{n} is multiplicative, then we have α(n) = |A_{n}| = |A_{n}(m_{1})∩A_{n}(m_{2})| = |A_{m_{1}}|·|A_{m_{2}}| = α(m_{1})α(m_{2}). Thus, the associated function α is multiplicative.

Now we define two conditions on {A_{n}}_{n} that will be sufficient to show that {A_{n}}_{n} is multiplicative.

MT1. For positive integers m and n, if m divides n and a ∈ A_{n}, then a mod m ∈ A_{m}, where a mod m is the residue of a when a is divided by m.

MT2. If n = m_{1}m_{2} where m_{1} and m_{2} are relatively prime, and if a_{1} ∈ A_{m_{1}}, a_{2} ∈ A_{m_{2}} and a is the unique solution in I_{n} to the system of congruences x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}), then a ∈ A_{n}.

Note that if {A_{n}}_{n} satisfies condition MT1 and m divides n, then A_{n} ⊆ A_{n}(m).

Lemma 5. If {A_{n}}_{n} satisfies MT1 and MT2, then {A_{n}}_{n} is multiplicative.

Proof. Let us suppose that n = m_{1}m_{2} for relatively prime m_{1} and m_{2}. Since {A_{n}}_{n} satisfies MT1, we have A_{n} ⊆ A_{n}(m_{1}) ∩ A_{n}(m_{2}). To prove the other inclusion, let us take a ∈ A_{n}(m_{1}) ∩ A_{n}(m_{2}). Then, there exist a_{1} ∈ A_{m_{1}} and a_{2} ∈ A_{m_{2}} such that a ≡ a_{1} (mod m_{1}) and a ≡ a_{2} (mod m_{2}) and, since {A_{n}}_{n} satisfies MT2, it follows that a ∈ A_{n}. This shows that A_{n} = A_{n}(m_{1}) ∩ A_{n}(m_{2}). Hence, {A_{n}}_{n} is multiplicative.

If we assume that the family of sets {A_{n}}_{n} satisfy conditions MT1 and MT2, then, by Lemmas 4 and 5, the associated function α is multiplicative. Thus, to determine the values of α on all positive integers, it is enough to determine α(p^{n}) for all primes p, and n ≥ 1. This leads us to study the sets A_{p^{n}} for powers of primes p^{n}.

Condition MT1 on the family {A_{n}}_{n} implies that if p is prime and n ≥ 1, then A_{p^{n}} ⊆ A_{p^{n}}(p^{n−1}). For n ≥ 1, we define N_{p^{n}} := A_{p^{n}}(p^{n−1}) \ A_{p^{n}} and call these sets, the N-sets of the prime p.

Lemma 6. Let p be a prime number and n ≥ 1. Then

α(p^{n}) = pα(p^{n−1}) − |N_{p^{n}}|.

Proof. The size of A_{p^{n}}(p^{n−1}) is p · |A_{p^{n−1}}| = pα(p^{n−1}). Then

α(p^{n}) = |A_{p^{n}}(p^{n−1}) \ N_{p^{n}}| = |A_{p^{n}}(p^{n−1})| − |N_{p^{n}}| = pα(p^{n−1}) − |N_{p^{n}}|.

Now, we focus on the sizes of the sets N_{p^{n}} for n ≥ 1.

We are interested in those families of sets {A_{n}}_{n}, where A_{n} is the set of elements a ∈ I_{n} such that the congruence f(x_{1}, x_{2}, …, x_{t}) ≡ a (mod n) is solvable. We refer to the function α associated with this family {A_{n}}_{n}, as the function associated with f(x_{1}, x_{2}, …, x_{t}).

Proposition 7. The family {A_{n}}_{n} associated with a polynomial f(x_{1}, x_{2}, …, x_{t}) is multiplicative. In particular, the function α associated with f(x_{1}, x_{2}, …, x_{t}) is multiplicative.

Proof. The family {A_{n}}_{n} associated with f(x_{1}, x_{2}, …, x_{t}) trivially satisfies MT1. Towards MT2, assume that f(a_{1}, a_{2}, …, a_{t}) ≡ a_{1} (mod m_{1}) and f(b_{1}, b_{2}, …, b_{t}) ≡ a_{2} (mod m_{2}), where a_{i}, b_{j} ∈ ℤ, m_{1} and m_{2} are relatively prime, n = m_{1}m_{2}, a_{i} ∈ I_{m_{i}}, i = 1, 2. Let a be the only solution in I_{n} of the system of congruences x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}). By the Chinese remainder theorem, for each j = 1, 2, …, t, there exists c_{j} ∈ ℤ such that c_{j} ≡ a_{j} (mod m_{1}) and c_{j} ≡ b_{j} (mod m_{2}). Since f is a polynomial, f(c_{1}, c_{2}, …, c_{t}) ≡ f(a_{1}, a_{2}, …, a_{t}) ≡ a_{1} ≡ a (mod m_{1}) and f(c_{1}, c_{2}, …, c_{t}) ≡ f(b_{1}, b_{2}, …, b_{t}) ≡ a_{2} ≡ a (mod m_{2}). It follows that f(c_{1}, c_{2}, …, c_{t}) ≡ a (mod n), that is, a ∈ A_{n}. The result follows by Lemmas 4 and 5.

Remark 8. Let us consider r families {A_{n}^{(i)}}_{n}, i = 1, 2, …, r, where A_{n}^{(i)} ⊆ I_{n}. For each n ≥ 1, we set A_{n} := ⋂_{i=1}^{r} A_{n}^{(i)}. Assume that A_{n} ≠ ∅ for all n. If the r families satisfy MT1 (resp. MT2), then the family {A_{n}}_{n} satisfy MT1 (resp. MT2).

When {A_{n}^{(i)}}_{n} is the family associated with some polynomial f_{i}(x_{1}^{(i)}, …, x_{t_{i}}^{(i)}), and the intersections A_{n} = ⋂_{i=1}^{r} A_{n}^{(i)} are nonempty, the family {A_{n}}_{n} is multiplicative. In this case, the associated function α counts the number of elements a ∈ I_{n} such that the system of congruences

f_{i}(x_{1}^{(i)}, …, x_{t_{i}}^{(i)}) ≡ a (mod n), i = 1, 2, …, r

is solvable.

2.2 The multiplicative family associated with c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}

We now study the multiplicative function α and the sets A_{p^{n}} associated with a polynomial of the form f(x_{1}, x_{2}, …, x_{t}) = c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}, where c_{1}, c_{2}, …, c_{t} ∈ ℤ, k ≥ 1. To determine the value of α at prime powers, we need to understand the sets A_{p^{n}} and N_{p^{n}}. The following lemmas give useful properties of these sets.

Lemma 9. Let {A_{n}}_{n} be the family associated with the polynomial c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}. Let p be a prime number that does not divide c_{1}, c_{2}, …, c_{t} and let s be the highest nonnegative integer such that p^{s} divides k. Suppose a ∈ A_{p^{n}} and

c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ a (mod p^{n}),

where m_{1}, m_{2} …, m_{t} ∈ ℤ, and suppose that at least one m_{i} is not divisible by p. If n ≥ 2s+1, then a + jp^{n} ∈ A_{p^{n+1}} for all j such that 0 ≤ j < p.

Proof. Suppose that c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ a (mod p^{n}). Then, there is some integer w such that c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} = a + wp^{n}. Assume that p does not divide m_{1}. Write k = p^{s}k_{0}, where s ≥ 0 and p does not divide k_{0}. Let 0 ≤ j < p. Since p does not divide c_{1}m_{1}^{k−1}k_{0}, the congruence c_{1}m_{1}^{k−1}k_{0}x + w ≡ j (mod p) has solution for x in ℤ; so, there are integers d and e such that c_{1}m_{1}^{k−1}k_{0}d + w = j + ep. By the binomial theorem,

(m_{1} + dp^{n−s})^{k} = m_{1}^{k} + km_{1}^{k−1}dp^{n−s} + ∑_{2≤t≤k} \binom{k}{t}m_{1}^{k−t}d^{t}p^{t(n−s)}

= m_{1}^{k} + m_{1}^{k−1}k_{0}dp^{n} + ∑_{2≤t≤k} \binom{k}{t}m_{1}^{k−t}d^{t}p^{t(n−s)}.

Since n ≥ 2s + 1, for t ≥ 2 we have t(n − s) ≥ 2(n − s) = n + (n − 2s) ≥ n + 1. Then

(m_{1} + dp^{n−s})^{k} ≡ (m_{1}^{k} + m_{1}^{k−1}k_{0}dp^{n}) (mod p^{n+1}).

Therefore, modulo p^{n+1}, we have

c_{1}(m_{1} + dp^{n−s})^{k} + ⋯ + c_{t}m_{t}^{k} ≡ (c_{1}m_{1}^{k} + ⋯ + c_{t}m_{t}^{k}) + c_{1}m_{1}^{k−1}k_{0}dp^{n}
≡ a + wp^{n} + c_{1}m_{1}^{k−1}k_{0}dp^{n}
≡ a + (w + c_{1}m_{1}^{k−1}k_{0}d)p^{n}
≡ a + jp^{n} + ep^{n+1}
≡ a + jp^{n}.

Hence, a + jp^{n} ∈ A_{p^{n+1}}.

Lemma 10. Let p be a prime number and consider the N-sets N_{p^{n}} associated with the polynomial c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}. If p does not divide c_{1}, …, c_{t}, then

N_{p^{n}} ⊆ {p^{k}a : a ∈ N_{p^{n−k}}},

for every n > k + 1.

Proof. If b ∈ N_{p^{n}}, then b ∈ A_{p^{n}}(p^{n−1}) and thus, b = c+jp^{n−1} for some c ∈ A_{p^{n−1}} and 0 ≤ j < p. Since c ∈ A_{p^{n−1}}, there are integers m_{1}, …, m_{t} such that c_{1}m_{1}^{k} +⋯+c_{t}m_{t}^{k} ≡ c (mod p^{n−1}). Note that if p^{s} is the highest power of p that divides k, then k ≥ p^{s} ≥ 2^{s} ≥ 2s; thus, if n > k + 1, then n − 1 ≥ 2s + 1. Therefore, if some m_{i} is not divisible by p, then by Lemma 9, b = c + jp^{n−1} ∈ A_{p^{n}}, a contradiction. It follows that all the m_{i} are divisible by p. Since n − 1 > k, we have p^{k} divides c and we get the congruence c_{1}(m_{1}/p)^{k} + ⋯ + c_{t}(m_{t}/p)^{k} ≡ c/p^{k} (mod p^{n−k−1}). Hence c/p^{k} ∈ A_{p^{n−k−1}}.

We claim that c/p^{k} + jp^{n−k−1} ∈ N_{p^{n−k}}. On the contrary, if c_{1}q_{1}^{k} + ⋯ + c_{t}q_{t}^{k} ≡ c/p^{k} + jp^{n−k−1} (mod p^{n−k}) for some integers q_{1}, …, q_{t}, then by multiplying by p^{k} we obtain that c_{1}(pq_{1})^{k} + ⋯ + c_{t}(pq_{t})^{k} ≡ c + jp^{n−1} (mod p^{n}), that is, b = c + jp^{n−1} ∈ A_{p^{n}}, a contradiction. Thus, if a := c/p^{k} + jp^{n−k−1}, then a ∈ N_{p^{n−k}} and b = c + jp^{n−1} = p^{k}a. This ends the proof.

We now define a condition on the prime p and the polynomial, in such a way that the reverse inclusion in Lemma 10 holds. Most of the cases we are interested in satisfy this condition. When this condition fails, we must find another way to tackle the problem of finding α(p^{n}) for n ≥ 1.

Let p be a prime and f(x_{1}, …, x_{t}) be any polynomial with coefficients in ℤ. We say that a non-negative integer e is an exponent of p in f(x_{1}, …, x_{t}), if whenever p^{e} divides an integer of the form f(m_{1}, …, m_{t}), then the quotient f(m_{1}, …, m_{t})/p^{e} is also of the form f(q_{1}, …, q_{t}) for some integers q_{1}, …, q_{t}.

Lemma 11. The following statements are true.

1. For every prime number p and k ≥ 1, k is an exponent of p in x^{k}.

2. If p = 2 or p is prime with p ≡ 1 (mod 4), then 1 is an exponent of p in the polynomial x^{2} + y^{2}.

3. If p is prime and p ≡ 3 (mod 4), then 2 is an exponent of p in the polynomial x^{2} + y^{2}.

4. The integer 2 is an exponent of the prime number 2 in the polynomial x^{2} + y^{2} + z^{2}.

Proof. (1) If p^{k} divides m^{k}, then p divides m and m^{k}/p^{k} = (m/p)^{k}.

(2) If p divides an integer of the form x^{2} + y^{2}, then (x^{2} + y^{2})/p is a sum of two squares by Theorem 1.

(3) If p ≡ 3 (mod 4) divides an integer of the form x^{2} + y^{2}, then (x^{2} + y^{2})/p^{2} is a sum of two squares by Theorem 1.

(4) Suppose 4 divides m_{1}^{2} + m_{2}^{2} + m_{3}^{2} for integers m_{1}, m_{2} and m_{3}. Then m_{1}^{2} + m_{2}^{2} + m_{3}^{2} is even, which implies that two out of the three integers m_{1}, m_{2} and m_{3} are odd and one is even, or the three, m_{1}, m_{2} and m_{3} are even. In the first case, say m_{1} = 2w_{1} + 1, m_{2} = 2w_{2} + 1 and m_{3} = 2w_{3}. Then, we have m_{1}^{2}+m_{2}^{2}+m_{3}^{2} = 4(w_{1}^{2}+w_{2}^{2}+w_{1}+w_{2}+w_{3}^{2})+2, which is not divisible by 4. Hence, m_{1}, m_{2} and m_{3} are even. So, we can write m_{1} = 2w_{1}, m_{2} = 2w_{2}, m_{3} = 2w_{3} and, therefore, m_{1}^{2} + m_{2}^{2} + m_{3}^{2} = 4(w_{1}^{2} + w_{2}^{2} + w_{3}^{2}). This ends the proof.

Note that if e is an exponent of a prime p in a polynomial f(x_{1}, x_{2}, …, x_{t}), then any positive multiple of e is also an exponent of p in f(x_{1}, x_{2}, …, x_{t}).

Lemma 12. If an exponent e of a prime p in the polynomial c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, then {p^{k}a : a ∈ N_{p^{n−k}}} ⊆ N_{p^{n}} for n > k.

Proof. If p^{k}a ∈ A_{p^{n}} where a ∈ N_{p^{n−k}}, then there are integers m_{1}, …, m_{t} such that c_{1}m_{1}^{k} + ⋯+c_{t}m_{t}^{k} ≡ p^{k}a (mod p^{n}). Since e divides k, we have k is an exponent of p in c_{1}x_{1}^{k}+⋯+c_{t}x_{t}^{k}. Then, we can write (c_{1}m_{1}^{k} + ⋯ + c_{t}m_{t}^{k})/p^{k} = c_{1}q_{1}^{k} + ⋯ + c_{t}q_{t}^{k} for some integers q_{1}, …, q_{t}. Therefore, c_{1}q_{1}^{k} + ⋯ + c_{t}q_{t}^{k} ≡ a (mod p^{n−k}), that is, a ∈ A_{p^{n−k}}, a contradiction. Thus, p^{k}a ∈ N_{p^{n}} for all a ∈ N_{p^{n−k}}.

An application of Lemma 10 and 12 tells us that if there is an exponent of p in c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} that divides k, then for all n > k + 1 we have

N_{p^{n}} = {p^{k}a : a ∈ N_{p^{n−k}}}.  (2)

For a set of integers A, mA denote the set {ma : a ∈ A}. Then N_{p^{n}} = p^{k}N_{p^{n−k}} for all n > k + 1. Therefore, if n = qk + r, where 2 ≤ r ≤ k + 1, we have

N_{p^{n}} = p^{k}N_{p^{n−k}} = p^{2k}N_{p^{n−2k}} = ⋯ = p^{kq}N_{p^{r}}.  (3)

We set n_{r} := |N_{p^{r}}|, for 2 ≤ r ≤ k + 1. By (3), it follows that if n > 1 and n ≡ r (mod k), then |N_{p^{n}}| = |N_{p^{r}}| = n_{r}.

Proposition 13. Let p be a prime and k ≥ 1. Suppose that some exponent e of p in the polynomial c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, and p does not divide c_{1}, …, c_{t}. Then

α(p^{n}) = pα(p^{n−1}) − n_{r}  (4)

for all n > 1 such that n ≡ r (mod k).

Proof. The result follows from the fact that |N_{p^{n}}| = |N_{p^{r}}| = n_{r} and Lemma 6.

It is not difficult to deduce, from (4), the following explicit formulas for α(p^{n}).

Corollary 14. Let p be a prime and k be a positive integer. Suppose that some exponent e of p in the polynomial c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, and p does not divide c_{1}, …, c_{t}. Let n be a positive integer.

(i) If n ≡ 1 (mod k), then

α(p^{n}) = p^{n−1}α(p) − \frac{p^{n−1} − 1}{p^{k} − 1} ∑_{j=2}^{k+1} n_{j}p^{k−j+1};

(ii) If n ≡ r (mod k) where 2 ≤ r ≤ k, then

α(p^{n}) = p^{n−1}α(p) − \frac{p^{n−1} − p^{r−1}}{p^{k} − 1} ∑_{j=2}^{k+1} n_{j}p^{k−j+1} − ∑_{j=2}^{r} n_{j}p^{r−j}.

For the sets N_{p^{r}} with 2 ≤ r ≤ k + 1, we have the following result.

Proposition 15. Consider the N-sets associated with the polynomial c_{1}x_{1}^{k} +c_{2}x_{2}^{k} +⋯+c_{t}x_{t}^{k}. Let p be a prime number that does not divide c_{1}, …, c_{t} and let p^{s} be the highest power of p that divides k. If 2s + 2 ≤ r ≤ k + 1, then

N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p}.

Moreover,

N_{p^{k+1}} ⊆ {jp^{k} : j ∉ A_{p}, 0 < j < p},

and if some exponent of p in c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, then

N_{p^{k+1}} = {jp^{k} : j ∉ A_{p}, 0 < j < p}.

Proof. Recall that A_{p^{r}} ⊆ A_{p^{r}}(p^{r−1}) and N_{p^{r}} = A_{p^{r}}(p^{r−1})\A_{p^{r}}. We show that a+jp^{r−1} ∈ A_{p^{r}} for any a ∈ A_{p^{r−1}} with a ≠ 0 and 0 ≤ j < p. In fact, if a ∈ A_{p^{r−1}} and a ≠ 0, then there are integers m_{1}, …, m_{t} such that

c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ a (mod p^{r−1}).

If p divides all the m_{i}, then p^{r−1} divides a, since r − 1 ≤ k. But 0 ≤ a < p^{r−1} and a ≡ 0 (mod p^{r−1}) imply a = 0, a contradiction. We conclude that some m_{i} is not divisible by p. So, by Lemma 9, we have a + jp^{r−1} ∈ A_{p^{r}} for any 0 ≤ j < p.

This implies that if a + jp^{r−1} ∈ N_{p^{r}}, then a = 0; therefore, all elements in N_{p^{r}} have the form jp^{r−1}, where 0 ≤ j < p. Thus, we have N_{p^{r}} ⊆ {jp^{r−1} : 0 ≤ j < p}. Since 0 ∉ N_{p^{r}}, we conclude that N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p}.

In the case where r = k+1, if j ∈ A_{p}, 0 < j < p, then c_{1}m_{1}^{k}+c_{2}m_{2}^{k}+⋯+c_{t}m_{t}^{k} ≡ j (mod p) for some integers m_{1}, …, m_{t}. Hence, c_{1}(pm_{1})^{k} +c_{2}(pm_{2})^{k} +⋯+c_{t}(pm_{t})^{k} ≡ jp^{k} (mod p^{k+1}), and this shows that jp^{k} ∈ A_{p^{k+1}}. Thus, N_{p^{k+1}} ⊆ {jp^{k} : j ∉ A_{p}, 0 < j < p}.

Finally, if we have c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ jp^{k} (mod p^{k+1}) for some m_{1}, m_{2}, …, m_{t}, and (c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k})/p^{k} = c_{1}q_{1}^{k} + c_{2}q_{2}^{k} + ⋯ + c_{t}q_{t}^{k} for some integers q_{1}, q_{2}, …, q_{t}, then c_{1}q_{1}^{k} + c_{2}q_{2}^{k} + ⋯ + c_{t}q_{t}^{k} ≡ j (mod p), which shows that j ∈ A_{p} if and only if jp^{k} ∈ A_{p^{k+1}}. Hence, N_{p^{k+1}} = {jp^{k} : j ∉ A_{p}, 0 < j < p}.

If p does not divide k in Proposition 15, then s = 0 and the inclusion N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p} holds for 2 ≤ r ≤ k + 1.

To determine the values α(p^{n}) for all n ≥ 1 (if the conditions of Proposition 13 hold), our strategy is composed by the following steps:

1. Determine α(p) = |A_{p}|. Here, we have to determine A_{p} separately.

2. Determine the sets N_{p^{r}} for r = 2, …, k + 1. Then n_{r} = |N_{p^{r}}| for r = 2, …, k + 1

3. We apply (4) to obtain a recurrence formula for α(p^{n}).

4. We find an explicit formula for α(p^{n}) from the recurrence formula in step (3), or using Corollary 14.

2.3 The polynomial x^{k}

We illustrate our ideas by considering the multiplicative function α of the polynomial f(x) = x^{k}, where k ≥ 1 is a given integer. For simplicity, we assume that p is any prime that does not divide k.

The steps we follow are

1. Determine A_{p} and α(p).

2. Determine N_{p^{2}}, …, N_{p^{k+1}} and the numbers n_{2}, …, n_{k+1}.

3. Determine the recurrence given by (4).

4. Give explicit formulas for α(p^{n}).

For the first step, we have A_{p} is the set of elements a ∈ I_{p} = {0, 1, …, p − 1} such that the congruence x^{k} ≡ a (mod p) is solvable. If a ≠ 0, then a is a k-th power residue modulo p. Therefore, we have A_{p} = {a ∈ I_{p} : a is a k-th power residue modulo p} ∪ {0}. If d = gcd(k, p − 1), then there are (p − 1)/d k-th power residues modulo p and so

α(p) = (p − 1)/d + 1.  (5)

Now, for the N-sets N_{p^{2}}, …, N_{p^{k+1}} we have the following result.

Lemma 16. Assume that p does not divide k. For r = 2, …, k,

N_{p^{r}} = {jp^{r−1} : 0 < j < p}.

Moreover

N_{p^{k+1}} = {jp^{k} : 0 < j < p and j ∉ A_{p}}.

Proof. Since p does not divide k and k is an exponent of p in x^{k}, by Proposition 15 we have N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p} for r = 2, …, k and N_{p^{k+1}} = {jp^{k} : 0 < j < p and j ∉ A_{p}}.

To prove that {jp^{r−1} : 0 < j < p} ⊆ N_{p^{r}} when 2 ≤ r ≤ k, let us take 0 < j < p and assume that jp^{r−1} ∈ A_{p^{r}}. Then m^{k} ≡ jp^{r−1} (mod p^{r}) for some integer m. So, p divides m and since k ≥ r, we deduce that p^{r} divides jp^{r−1}. Therefore, p divides j, which is a contradiction. Hence jp^{r−1} ∈ N_{p^{r}}.

For r = 2, …, k + 1, we set n_{r} = |N_{p^{r}}|. From Lemma 16 and (5) it follows that

n_{r} = \begin{cases}p − 1, & for r = 2, …, k; \\ (d − 1)(p − 1)/d, & for r = k + 1. \end{cases}

By Proposition 13 and Corollary 14 we get our recurrence formula, and it is not difficult to deduce the explicit formula in the following proposition.

Proposition 17. Let p be a prime, n, k ≥ 1 and d = gcd(k, p − 1). If α is the multiplicative function associated with the polynomial x^{k}, then we have the following recurrence formula

α(p^{n}) = \begin{cases}pα(p^{n−1}) − (d − 1)(p − 1)/d, & if n ≡ 1 (mod k); \\ pα(p^{n−1}) − p + 1, & if n ≢ 1 (mod k). \end{cases}

Moreover, if n ≡ r (mod k) where 1 ≤ r ≤ k, then

α(p^{n}) = \frac{p^{n+k−1} − p^{r−1}}{d · (\frac{p^{k}−1}{p−1})} + 1.  (6)

Remark 18. We can determine α(p^{n}) in the general case (without the restriction that p does not divide k) in the following way. Let P (k, m) be the set of k-th power residues modulo m. We have that, for 0 < a < p^{n}, the congruence x^{k} ≡ a (mod p^{n}) is solvable if and only if there exist r ≥ 0 such that rk ≤ n and b ∈ P (k, p^{n−rk}) such that a = p^{rk}b. To see this, if x^{k} ≡ a (mod p^{n}) is solvable and p does not divide a, we take r = 0 and b = a. In case p divides a, we find that p divides x and the congruence (x/p)^{k} ≡ a/p^{k} (mod p^{n−k}) is solvable. If p does not divide a/p^{k}, we take r = 1 and b = a/p^{k}. If we continue in this way we obtain the desired result. It follows that

A_{p^{n}} = \{0\} ∪ ⋃_{r=0}^{⌊ \frac{n}{k} ⌋} p^{rk}P (k, p^{n−rk}),

and therefore,

α(p^{n}) = 1 + ∑_{r=0}^{⌊ \frac{n}{k} ⌋} |P (k, p^{n−rk})|.

For instance, assume p is odd, k = p^{s} where s ≥ 1 and k does not divide n. Then, for r ≥ 0 we have

|P (k, p^{n−rk})| = \frac{p^{n−rk−1}(p − 1)}{gcd(p^{n−rk−1}(p − 1), p^{s})} = \begin{cases}p − 1, & if n − rk − 1 ≤ s; \\ p^{n−rk−s−1}(p − 1), & if n − rk − 1 > s. \end{cases}

See, for example, [5, Chapter 4, Sec. 2]. So, we can write

α(p^{n}) = 1 + ∑_{0≤r<⌈ \frac{n−s−1}{k} ⌉} p^{n−rk−s−1}(p − 1) + ∑_{⌈ \frac{n−s−1}{k} ⌉≤r≤⌊ \frac{n}{k} ⌋}(p − 1).

3 Sums and differences of squares

In this section we apply our ideas to the polynomials x^{2} + y^{2}, x^{2} + y^{2} + z^{2} and x^{2} − y^{2}. In each case, we determine formulas for α(p^{n}). We also show how to determine explicitly the sets A_{p^{n}} and answer the question about determining all n such that the given polynomial is surjective on n.

3.1 The polynomial x^{2} + y^{2}

We consider the polynomial f(x, y) = x^{2} + y^{2} and its associated function α. By using our method, we obtain the results about the size of the sets A_{p^{n}} found in [3, 4].

Lemma 19. For any prime number p, we have α(p) = p.

Proof. Let us show that every element in I_{p} = {0, 1, …, p − 1} is expressible as the sum of two squares modulo p. It is known that there are (p + 1)/2 elements in I_{p} that are squares modulo p. Then, for a given a ∈ I_{p}, there are (p + 1)/2 elements in I_{p} that are expressible as a − x^{2} modulo p. Since 2(p + 1)/2 = p + 1 and I_{p} has p elements, there is an element in I_{p} that is expressible simultaneously as a − x^{2} and y^{2} modulo p, for some x, y ∈ I_{p}. This implies that x^{2} + y^{2} ≡ a (mod p).

We now calculate α(2^{n}) for all n ≥ 1. By Lemma 11, the prime 2 has exponent 1 in x^{2} + y^{2}.

An easy computation gives us the following:

A_{2} = {0, 1}, A_{4} = {0, 1, 2}, A_{8} = {0, 1, 2, 4, 5}.

and

A_{4}(2) = {0, 1, 2, 3}, A_{8}(4) = {0, 1, 2, 4, 5, 6}.

Then, N_{4} = {3} and N_{8} = {6}, that is, n_{2} = 1 and n_{3} = 1. Now, by applying Corollary 14, for n odd we have

α(2^{n}) = 2^{n−1}α(2) − \frac{2^{n−1} − 1}{2^{2} − 1}(2 + 1)
= 2^{n} − (2^{n−1} − 1)
= 2^{n−1} + 1,

and for n even

α(2^{n}) = 2^{n−1}α(2) − \frac{2^{n−1} − 2}{2^{2} − 1}(2 + 1) − 1
= 2^{n} − (2^{n−1} − 2) − 1
= 2^{n−1} + 1.

Therefore, for all n ≥ 1

α(2^{n}) = 2^{n−1} + 1.

Remark 20. By applying our method we obtain explicit descriptions of the sets A_{2^{n}} for all n ≥ 1, as follows. First of all, we determine N_{2^{n}} for all n ≥ 2. Note that N_{2^{2}} = {3 · 2^{2−2}} and N_{2^{3}} = {3 · 2^{3−2}}. For n > 3, we can write n = 2q + r, where r ∈ {2, 3}. It follows by (3) that N_{2^{n}} = {2^{2q}a : a ∈ N_{2^{r}}} = {2^{n−r}a : a ∈ N_{2^{r}}}. Then, it is easy to see that

N_{2^{n}} = {3 · 2^{n−2}} = {2^{n−2} + 2^{n−1}}

for all n ≥ 2.

We recall that

A_{2^{n}} = {a + a_{n−1}2^{n−1} : a ∈ A_{2^{n−1}}, a_{n−1} ∈ {0, 1}} \ N_{2^{n}}.

By an induction argument on n, it is not difficult to show that for all n ≥ 1, A_{2^{n}} consists of all elements of the form

a_{0} + a_{1} · 2 + a_{2} · 2^{2} + ⋯ + a_{n−1} · 2^{n−1}  (7)

where

1. a_{0}, a_{1}, a_{2}, …, a_{n−1} ∈ {0, 1},

2. a_{0} + a_{1} · 2 + a_{2} · 2^{2} + ⋯ + a_{i−1} · 2^{i−1} ∈ A_{2^{i}}, i = 1, …, n − 1.

Now, assume that an element of the form (7) is not in A_{2^{n}}. Then there is some i, 2 ≤ i ≤ n, such that a_{0} + a_{1} · 2 + a_{2} · 2^{2} + ⋯ + a_{i−1} · 2^{i−1} ∈ N_{2^{i}}. Since N_{2^{i}} = {2^{i−2} + 2^{i−1}}, we see that a_{0} = ⋯ = a_{i−3} = 0 and a_{i−2} = a_{i−1} = 1. So,

a_{0} + a_{1} · 2 + a_{2} · 2^{2} + ⋯ + a_{n−1} · 2^{n−1} = 2^{i−2} + 2^{i−1} + a_{i}2^{i} + ⋯ + a_{n−1}2^{n−1}.

Conversely, all elements of the form 2^{i−2}+2^{i−1}+a_{i}2^{i}+⋯+a_{n−1}2^{n−1}, where a_{i}, …, a_{n−1} ∈ {0, 1} are not in A_{2^{n}}. Therefore, A_{2^{n}} is the set of all integers of the form (7) such that the first two nonzero coefficients are not consecutive.

With this description of A_{2^{n}}, we can also calculate α(2^{n}). In fact, there are 2^{n−i−2} elements of the form 2^{i−2} + 2^{i−1} + a_{i}2^{i} + ⋯ + a_{n−1}2^{n−1} for 2 ≤ i ≤ n. So,

α(2^{n}) = 2^{n} − ∑_{i=2}^{n} 2^{n−i} = 2^{n} − (2^{n−1} − 1) = 2^{n−1} + 1.

Now, we compute α(p^{n}) where p is an odd prime. In this case, the highest power of p that divides 2 is p^{0}, so by Proposition 15 we have N_{p^{2}} ⊆ {jp : 0 < j < p} and N_{p^{3}} = ∅, since A_{p} = I_{p} by Lemma 19.

Proposition 21. Let p be a prime such that p ≡ 3 (mod 4) and n ≥ 2. Then N_{p^{2}} = {jp : 0 < j < p} and N_{p^{3}} = ∅. The recurrence formula for α(p^{n}) is given by

α(p^{n}) = \begin{cases}pα(p^{n−1}), & if n is odd; \\ pα(p^{n−1}) − p + 1, & if n is even. \end{cases}

An explicit formula for α(p^{n}) is

α(p^{n}) = \begin{cases}\frac{p}{p+1}(p^{n} + 1), & if n is odd; \\ \frac{1}{p+1}(p^{n+1} + 1), & if n is even. \end{cases}

Proof. It only remains to prove that {jp : 0 < j < p} ⊆ N_{p^{2}}, that is, jp ∉ A_{p^{2}} if 0 < j < p. By contradiction, assume that jp ∈ A_{p^{2}}. Then, there are integers m_{1}, m_{2} and w such that m_{1}^{2} +m_{2}^{2} = jp+wp^{2}. This implies that p divides m_{1}^{2} +m_{2}^{2}, and by Theorem 1, p appears with even exponent in the prime decomposition of m_{1}^{2} + m_{2}^{2}. In particular, p^{2} divides m_{1}^{2} + m_{2}^{2}, and the equation m_{1}^{2} + m_{2}^{2} = jp + wp^{2} implies that p divides j, a contradiction. This proves that N_{p^{2}} = {jp : 0 < j < p}.

We have n_{2} = p − 1 and n_{3} = 0. By Proposition 13, we obtain a recurrence formula for α(p^{n})

α(p^{n}) = \begin{cases}pα(p^{n−1}), & if n is odd; \\ pα(p^{n−1}) − p + 1, & if n is even. \end{cases}

Note that α(p^{0}) = 1. Then, it is easy to deduce the explicit formula

α(p^{n}) = \begin{cases}\frac{p}{p+1}(p^{n} + 1), & if n is odd; \\ \frac{1}{p+1}(p^{n+1} + 1), & if n is even. \end{cases}

Let p be a prime number such that p ≡ 3 (mod 4). We can give a description of the set A_{p^{n}} for n ≥ 1. By proceeding as in the case of A_{2^{n}}, we have A_{p^{n}} consists of all integers of the form

a_{0} + a_{1} · p + a_{2} · p^{2} + ⋯ + a_{n−1} · p^{n−1}  (8)

where

1. a_{0}, a_{1}, a_{2}, …, a_{n−1} ∈ {0, 1, …, p − 1},

2. a_{0} + a_{1} · p + a_{2} · p^{2} + ⋯ + a_{i−1} · p^{i−1} ∈ A_{p^{i}}, i = 1, …, n − 1.

By induction on n, and using that N_{p^{n}} = p^{2}N_{p^{n−2}} for n > 3, N_{p^{2}} = {jp : 0 < j < p} and N_{p^{3}} = ∅, we obtain that

N_{p^{n}} = \begin{cases}∅, & if n > 1 is odd; \\ \{jp^{n−1} : 0 < j < p\}, & if n is even. \end{cases}

This implies that an element of the form (8) is in A_{p^{n}} if and only if its first nonzero term has the form a_{i}p^{i} with i even.

Proposition 22. Let p be a prime such that p ≡ 1 (mod 4) and n be a positive integer. Then, N_{p^{2}} = N_{p^{3}} = ∅. Moreover, α(p^{n}) = p^{n} for all n ≥ 1.

Proof. We know that N_{p^{3}} = ∅. To prove that N_{p^{2}} = ∅, it remains to prove that jp ∈ A_{p^{2}} if 0 < j < p. In fact, if 0 < j < p, then, by Lemma 19, there are integers w_{1}, w_{2} and w such that w_{1}^{2}+w_{2}^{2} = j+wp. Since p ≡ 1 (mod 4), by Theorem 1, the product p(w_{1}^{2}+w_{2}^{2}) is a sum of two squares, say p(w_{1}^{2}+w_{2}^{2}) = m_{1}^{2}+m_{2}^{2}. Therefore, m_{1}^{2}+m_{2}^{2} = p(w_{1}^{2}+w_{2}^{2}) = p(j +wp) = jp+wp^{2}. Thus, we have shown A_{p^{2}} = I_{p^{2}} and therefore, N_{p^{2}} = ∅.

By Proposition 13, the following recurrence formula holds

α(p^{n}) = \begin{cases}p, & if n = 1; \\ pα(p^{n−1}), & if n > 1. \end{cases}

This implies that α(p^{n}) = p^{n} for all n ≥ 1.

3.2 The polynomial x^{2} + y^{2} + z^{2}

In this section we consider the polynomial f(x, y, z) = x^{2}+y^{2}+z^{2} and its associated function α.

By Lemma 11 we have 2 is an exponent of the prime 2 in x^{2} + y^{2} + z^{2}. By direct computations, we check easily that A_{2} = {0, 1}, A_{4} = {0, 1, 2, 3}, A_{8} = {0, 1, 2, 3, 4, 5, 6}, and we see that N_{4} = ∅ and N_{8} = {7}. From Proposition 13, it follows that

α(2^{n}) = \begin{cases}2, & if n = 1; \\ 2α(2^{n−1}), & if n is even; \\ 2α(2^{n−1}) − 1, & if n > 2 is odd. \end{cases}

The corresponding explicit formula is

α(2^{n}) = \begin{cases}\frac{1}{3}(5 · 2^{n−1} + 1), & if n is odd; \\ \frac{2}{3}(5 · 2^{n−2} + 1), & if n is even. \end{cases}

We now describe explicitly the sets A_{2^{n}}. It is not difficult to show that

N_{2^{n}} = \begin{cases}∅, & if n is even; \\ \{7 · 2^{n−3}\}, & if n ≥ 2 is odd. \end{cases}

For n ≥ 2 odd, we have N_{2^{n}} = {2^{n−3} + 2^{n−2} + 2^{n−1}}. So the set A_{2^{n}} consists of all integers a_{0} + a_{1}2 + ⋯ + a_{n−1}2^{n−1} that are not of the form 2^{i} + 2^{i+1} + 2^{i+2} + a_{i+3}2^{i+3} + ⋯ + a_{n−1}2^{n−1} for some odd i with 0 ≤ i ≤ n − 3.

Now, we consider the case where p is an odd prime. We cannot apply Proposition 13 because there is no exponent of p in x^{2} + y^{2} + z^{2}, so we treat this case in a slightly different way using Lemma 10. In order to do this, we take into account that odd primes are divided into 4 families depending on their residue modulo 8. The multiplication table of {1, 3, 5, 7} modulo 8 is shown in Table 1.

1 3 5 7
1 1 3 5 7
3 3 1 7 5
5 5 7 1 3
7 7 5 3 1

Table 1: Multiplication modulo 8

Recall that, by Theorem 2, a nonnegative integer is representable as the sum of three squares if and only if it is not of the form 4^{a}(8b + 7). From Table 1, we can deduce the following facts:

1. Dividing a number that is not of the form 4^{a}(8b + 7) by a prime of the form 8k + 1, gives a number that is not of the form 4^{a}(8b + 7). That is, if p is a prime of the form 8k + 1, then 1 is an exponent of p in x^{2} + y^{2} + z^{2}.

2. Dividing a number that is not of the form 4^{a}(8b + 7) by the square of a prime of the form 8k+3, 8k+5 or 8k+7 gives a number that is not of the form 4^{a}(8b+7). Thus, if p is a prime of the form 8k +3, 8k +5 or 8k +7, then 2 is an exponent of p in x^{2} +y^{2} +z^{2}.

Lemma 23. If p is an odd prime and m is a sum of three squares, then there exists c ∈ ℤ such that pm − cp^{2} is the sum of three squares.

Proof. If pm is a sum of three squares, then we can take c = 0. Suppose that pm is not the sum of three squares. Then one of the following cases holds:

1. p is of the form 8k + 3 and m is of the form 4^{a}(8b + 5),

2. p is of the form 8k + 5 and m is of the form 4^{a}(8b + 3),

3. p is of the form 8k + 7 and m is of the form 4^{a}(8b + 1).

We will show that in any case, pm−2p^{2} is not of the form 4^{a}(8b+7). If a > 0, then pm−2p^{2} is not divisible by 4, so pm − 2p^{2} is not of the form 4^{a}(8b + 7). Therefore, pm − 2p^{2} is a sum of three squares.

Now, assume that a = 0. In case 1 we have pm − 2p^{2} = (8k + 3)(8b + 5) − 2(8k + 3)^{2} = (8k + 3)[8(b − 2k − 1) + 7], which is a number of the form 8k + 5 and it is the sum of three squares. In case 2, pm − 2p^{2} = (8k + 5)(8b + 3) − 2(8k + 5)^{2} = (8k + 5)[8(b − 2k − 1) + 1], which is a number of the form 8k + 5 and it is also the sum of three squares. In case 3, pm − 2p^{2} = (8k + 7)(8b + 1) − 2(8k + 7)^{2} = (8k + 7)[8(b − 2k − 2) + 3], which is a number of the form 8k + 5 and it is the sum of three squares.

Proposition 24. Let p be an odd prime number. Then α(p^{n}) = p^{n} for all n ≥ 1.

Proof. First of all, by Lemma 19, every element in I_{p} = {0, 1, …, p − 1} is the sum of two squares modulo p and so, every element in I_{p} is the sum of three squares. This means that A_{p} = {0, 1, …, p − 1} and α(p) = p.

By Proposition 15, we have N_{p^{2}} ⊆ {jp : 0 < j < p} and N_{p^{3}} = ∅.

We show that jp ∈ A_{p^{2}} for all 0 < j < p. In fact, since j ∈ A_{p}, there are integers w_{1}, w_{2}, w_{3} and w_{4} such that w_{1}^{2} + w_{2}^{2} + w_{3}^{2} = j + w_{4}p. By Lemma 23, there exists c ∈ ℤ such that p(w_{1}^{2} + w_{2}^{2} + w_{3}^{2}) − cp^{2} = u_{1}^{2} + u_{2}^{2} + u_{3}^{2} for some integers u_{1}, u_{2} and u_{3}. Hence, u_{1}^{2} +u_{2}^{2} +u_{3}^{2} = p(w_{1}^{2} +w_{2}^{2} +w_{3}^{2})−cp^{2} = pj +w_{4}p^{2} −cp^{2} = jp+(w_{4} −c)p^{2}, and this shows that jp ∈ A_{p^{2}}. Thus, N_{p^{2}} = ∅ and, consequently, N_{p^{n}} = ∅ for all n ≥ 2. From this, it follows that α(p^{n}) = p^{n} for all n ≥ 1.

Now we can determine all integers n such that x^{2} + y^{2} + z^{2} is surjective on n. If we write n = 2^{s}m, where m is odd, then we have α(n) = α(2^{s})α(m) = α(2^{s})m. Thus, α(n) = n if and only if α(2^{s}) = 2^{s}, and this last equality holds if and only if s ≤ 2. Then, x^{2} + y^{2} + z^{2} is surjective on n if and only if n ≢ 0 (mod 8).

3.3 The polynomial x^{2} − y^{2}

We make the computations of α(p^{n}) for the function associated with the polynomial x^{2} − y^{2}. We will use the following result [1, Theorem 13.4].

Theorem 25. A positive integer n can be represented as the difference of two squares if and only if n is not of the form 4k + 2.

By Theorem 25, each element a ∈ I_{n} that is not of the form 4k + 2 belongs to A_{n}. So the only elements in I_{n} that possibly do not belong to A_{n} are those that have the form 4k + 2. It is easy to see that A_{2} = {0, 1}. So, α(2) = 2.

Proposition 26. For any integer n ≥ 2, A_{2^{n}} is the set of all elements in I_{2^{n}} that are not of the form 4k + 2. Moreover, for each n ≥ 2

α(2^{n}) = 3 · 2^{n−2}.  (9)

Proof. Let n ≥ 2. By Theorem 25, it only remains to prove that no element of the form 4k + 2 is in A_{2^{n}}. Suppose, on the contrary, that 4k + 2 ∈ A_{2^{n}} for some k. Then there are integers m_{1}, m_{2}, w such that m_{1}^{2} − m_{2}^{2} = 4k + 2 + w2^{n}. It follows that m_{1}^{2} − m_{2}^{2} is even. Then, m_{1} and m_{2} are even or both of them are odd. In any case we obtain that m_{1}^{2} − m_{2}^{2} is divisible by 4. This yields that 4 divides 2, which is absurd.

Now, we determine the size of A_{2^{n}}. The elements in I_{2^{n}} of the form 4k+2 are 2, 6, …, 2^{n}− 2. Then, there are 2^{n−2} elements in I_{2^{n}} of the form 4k + 2. Thus, α(2^{n}) = 2^{n} − 2^{n−2} = 3 · 2^{n−2}.

Lemma 27. If p is an odd prime, then p has exponent 1 in x^{2} − y^{2}.

Proof. Suppose p = 2r + 1 and p divides m_{1}^{2} − m_{2}^{2} for integers m_{1} and m_{2}. If (m_{1}^{2} − m_{2}^{2})/p is not a difference of two squares, then m_{1}^{2} − m_{2}^{2} = p(4k + 2) for some k, and m_{1}^{2} − m_{2}^{2} = (2r + 1)(4k + 2) = 4(2rk + r + k) + 2. This contradicts Theorem 25.

Proposition 28. If p is an odd prime, then α(p^{n}) = p^{n} for all n ≥ 1.

Proof. Let p be an odd prime. The proof that every element in I_{p} = {0, 1, …, p − 1} is a difference of two squares modulo p is similar to the proof of Lemma 19. In particular, it follows that α(p) = p.

By Proposition 15, we have N_{p^{2}} ⊆ {jp : 0 < j < p} and N_{p^{3}} = ∅.

We show that if 0 < j < p, then jp ∈ A_{p^{2}}. Since p is odd, p does not divide 4. This fact implies that there exists an integer b such that 4b ≡ j (mod p). Then 4b = j + wp for some w and

(p + b)^{2} − (p − b)^{2} = 4bp = jp + wp^{2},

which shows that jp ∈ A_{p^{2}}.

Thus, we have N_{p^{2}} = ∅. It follows that N_{p^{n}} = ∅ for all n ≥ 2 and α(p^{n}) = p^{n} for all n ≥ 1.

We now determine all integers n ≥ 1 such that x^{2} − y^{2} is surjective on n. Again, if we write n = 2^{s}m, where m is odd, then we have α(n) = α(2^{s})m. Therefore, α(n) = n if and only if α(2^{s}) = 2^{s}, which holds if and only if s ≤ 1. Thus, x^{2} − y^{2} is surjective on n if and only if n ≢ 0 (mod 4).

Remark 29. For the function α associated with a polynomial of the form ±x_{1}^{2} ± x_{2}^{2} ± ⋯ ± x_{t}^{2} with t ≥ 2, different from x^{2} + y^{2}, x^{2} − y^{2} and x^{2} + y^{2} + z^{2}, we have α(n) = n for all n. This is a consequence of Lagrange’s four-square theorem and the fact that every integer can be expressed in the form x^{2} + y^{2} − z^{2}.

4 Acknowledgments

The authors thank the referee for the useful suggestions that helped to improve this paper.

References

[1] D. M. Burton, Elementary Number Theory, 7th ed., McGraw-Hill, 2011.

[2] K. Broughan, Characterizing the sum of two cubes, J. Integer Sequences 6 (2003), Article 03.4.6.

[3] R. Burns, Representing numbers as the sum of squares and powers in the ring ℤ_{n},

   preprint, 2017. Available at https://arxiv.org/abs/1708.03930.

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

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

2010 Mathematics Subject Classification: Primary 11A07; Secondary 11B13, 11B37, 11B83. Keywords: polynomial congruence, recurrence formula, sum of squares.

Received February 21 2019; revised version received August 13 2019; September 11 2019. Published in Journal of Integer Sequences, September 23 2019.

Return to Journal of Integer Sequences home page.