# When is $\{x^2+y^k \mod n: x,y \in \mathbb{Z}/n\mathbb{Z}\} \neq \mathbb{Z}/n\mathbb{Z}$?

This question came about when I played around with the classic statement $$\exists x,y \in \mathbb{Z}: x^2+y^2 = n \implies n \not\equiv 3 \mod 4$$ which is straightforwardly shown to be true by considering which values squares can take modulo $$4$$. This leads to the obvious question: What about different powers of $$x$$ and $$y$$?

The question is more interesting than it seems at first sight: Let us consider $$\{x^2+y^k \mod n: x,y \in \mathbb{Z}/n\mathbb{Z}\}$$ for some natural number $$k \geq 2$$ in the scope of this question. We know that the modular approach above works if this set has $$ elements (let's call such $$(k,n)$$ informative). Before we get to the fun part of investigating patterns, we remark that $$\forall a \in \mathbb{N}: (k,n) \text{ informative} \implies (ak,n) \text{ informative}$$ since we can rewrite $$x^2 + y^{ak} \equiv x^2 + (y^{a})^{k} \mod n$$ and notice that this can take at most as many different values as $$x^2 + y^{k} \mod n$$ (i.e. if the set as defined above already has $$ values, multiples in the exponent can only restrict it further).

Fixing $$k$$ and trying to find out which $$n$$ give us informative tuples, we can reduce clutter in the following table by only including conditions on $$n$$ which are not already given by one of the divisors of $$k$$ (per the argument above). With this, we get the following informative tuples $$(k,n)$$:

$$\begin{array}{c|c} k & \text{cond. on n} \\ \hline 2 & n \text{ not squarefree} \\ 3 & - \\ 4 & n \equiv 0 \mod 5 \\ 5 & n \equiv 0 \mod 11 \\ 6 & n \equiv 0 \mod 7 \lor n \equiv 0 \mod 13 \\ 7 & - \\ 8 & n \equiv 0 \mod 17 \\ 9 & n \equiv 0 \mod 19 \lor n \equiv 0 \mod 37 \\ 10 & \text{no }\textbf{additional}\text{ conditions} \\ 11 & n \equiv 0 \mod 23 \\ \vdots & \vdots \\ 18 & \text{no }\textbf{additional}\text{ conditions} \\ 19 & - \\ 20 & n \equiv 0 \mod 21 \lor n \equiv 0 \mod 41 \\ 21 & n \equiv 0 \mod 43 \lor n \equiv 0 \mod 49 \\ \vdots & \vdots \\ 30 & n \equiv 0 \mod 151 \\ 31 & - \end{array}$$

A dash indicates that no tuples with the fixed $$k$$ exist. We remark the following things:

• In almost any case, the condition on $$n$$ seems to be of the form $$\mod ak+1$$ with $$ak+1$$ prime for some $$a \in \mathbb{N}$$.
• Since there are an infinite amount of primes in every arithmetic progression, there must be an upper bound to these conditions. I've tried things like $$a \leq \log_2(k)$$ and $$a \leq \log_2(k)+1$$, but there are always exceptions$${}^{*}$$.
• However, there seem to be exceptions like $$(21,49a)$$ being informative despite $$49$$ being a prime square. This has been solved in my answer.
• The (prime) $$p$$ such that $$(p,n)$$ is never informative seem to be indexed by A124273, i.e. $$(p,n) \text{ is never informative} \iff p | \prod_{j = 1}^{p} \frac{p_j^p-1}{p_j-1}$$ where $$p_j$$ denotes the $$j$$-th prime.

I have the following question:

How can we characterise $$(k,n)$$ for a given $$k$$ without brute-forcing all values of $$x$$ and $$y$$? Is the upper bound on $$a$$ easily figured out?

* In these two cases: $$(9,37)$$ being informative despite $$37 = 4 \cdot 9 + 1$$ with $$4 > \log_2(9)$$ resp. $$(6,19)$$ not being informative despite $$19 = 3 \cdot 6 +1$$ with $$3 \leq \log_2(6)+1$$.

Much of it's basically related to Fermat's "little" theorem: if $$y$$ is coprime to prime $$m$$, $$y^{m-1} \equiv 1 \mod m$$. In particular if $$n$$ is prime, $$y^{n-1} \equiv 0$$ (for $$y=0$$) or $$1$$ (for $$y = 1 \ldots n-1$$), and thus $$x^2 + y^{n-1}$$ is either a quadratic residue or a quadratic residue $$+1$$ mod $$n$$. If there are two consecutive non-residues mod $$n$$ (which is almost always the case), $$(n-1, n)$$ is informative.

When $$n$$ is not prime, you can consider $$m$$ that is some prime factor of $$n$$: if $$(m-1, m)$$ is informative (as in the paragraph above), then so is $$(m-1, n)$$.

• Right! How could I forget about Fermat? I need to go to bed now, but I will ponder it first thing in the morning. May 5, 2023 at 0:33
• "Which is almost always the case" can be improved to "always the case for prime $p \geq 4$" according to this MathOverflow thread. May 5, 2023 at 21:52

I'm going to document further findings in this answer.

Regarding the $$(21,49a)$$-phenomenon, it is explained by number theory, although in a pretty boring, elementary way: By Euler's theorem we know that for any $$n \in \mathbb{N}$$ and $$x \in \mathbb{Z}$$ with $$\gcd(x,n) = 1$$ $$x^{\phi(n)} \equiv 1 \mod n$$ where $$\phi$$ is the Euler totient function. Choosing $$n = p^2$$ for some prime $$p$$, we arrive at $$x^{p(p-1)} \equiv 1 \mod p^2 \implies 0 \equiv x^{p(p-1)} - 1 = \left(x^{\frac{p(p-1)}{2}} -1\right)\left(x^{\frac{p(p-1)}{2}}+1\right) \mod p^2$$ by elementary properties of $$\phi$$. Now using that $$p^2$$ needs to distribute over these two factors in some way, we conclude that $$x^{\frac{p(p-1)}{2}} \equiv \pm 1 \mod p^2 \text{ if } \gcd(x,p^2) = 1$$ since splitting the factors would immediately lead to a contradiction.

If $$\gcd(x,p^2) > 1$$ we instantly get $$p|x$$. Thus, since $$\frac{p(p-1)}{2} \geq 3$$ for $$p \geq 3$$, we also have $$p^2|x^{\frac{p(p-1)}{2}}$$ for such $$x$$. We conclude $$x^{\frac{p(p-1)}{2}} \in \{-1,0,1\} \mod p^2 \text{ if } p \geq 3 \text{ prime}$$

Plugging in $$p = 7$$ for example yields $$x^{21} \in \{-1,0,1\} \mod 49$$ giving a reason why $$x^2+y^{21} \mod 49$$ can't cover all necessary classes. This actually constitutes a proof of the informativeness of $$(\frac{p(p-1)}{2},p^2)$$! Why? Using the result in this MathOverflow answer with the most pessimistic constant $$\theta = 0$$, we can see that any prime $$p \geq 8$$ has a gap of at least three consecutive non-quadratic residues.

As pointed out by Robert Israel in his answer, we can use this "gap result" to prove informativeness of pairs $$(p-1,p)$$ for prime $$p \geq 4$$. By noticing that for prime $$2p+1$$ $$\begin{array}{ll} x^{p} \equiv a \mod 2p+1 &\implies 1 \equiv x^{2p} \equiv a^2 \mod 2p+1 \\ &\iff 0 \equiv (a-1)(a+1) = a^2-1 \mod 2p+1 \\ &\implies a \equiv \pm 1 \mod 2p+1 \\ \end{array}$$ we can use the same result to show informativeness of $$(p,2p+1)$$ for $$2p+1 \geq 8 \iff p \geq 4$$ prime. Generalizing this result is hard, since we then need to figure out the unpredictable roots of cyclotomic polynomials over finite fields.

But: It heuristically shows why for small $$a$$ in $$p = ak+1$$ prime we sometimes have informativeness, since the solutions of $$p^k \mod ak+1$$ are restricted to at most $$a$$ different values. If $$a$$ grows to big, it might start to cover all the possible residue classes; this makes informativeness unlikely the larger $$a$$ gets.