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

Question

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 $<n$ 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 $<n$ 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$.}

Answer 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)$.

Answer 2

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.