Interesting pattern within $m^n+1\equiv0\pmod n$ In recent days, I have been studying the properties of $m^n+h\equiv0\pmod n$ where $m,n\in\mathbb{N}$ and $h\in\mathbb{Z}$, and I have noticed that for the equation $m^n+1\equiv0\pmod n$, some even numbers n have solutions and some don't.(If $n$ is odd then $m=n-1$ is a solution.) After using a program to find the even numbers that have at least $1$ solution, I found that the list of required numbers starts with $2,10,26,34,50,58,74,82,106,122,130,146,170,178,194...$, and I noticed that the numbers in the list under $1000$ can all be written as a sum of exactly $2$ coprime square numbers. How can I prove for the general case, that for an even number $n$, $n$ can be written as a sum of exactly $2$ coprime square numbers if and only if $m^n+1\equiv0\pmod n$ has at least $1$ solution?
 A: Nice observation! Something else you might notice, which turns out to imply your observation, is that all of the odd prime factors of your numbers are $1 \bmod 4$: $\{ 5, 13, 17, 29, \dots \}$. And a final thing you might notice is that all of your numbers are themselves congruent to $2 \bmod 4$, or equivalently are even but not divisible by $4$. This turns out to be an exact characterization:

Proposition: If $n$ is an even positive integer, the following are equivalent:

*

*There exists an integer $m$ such that $m^n \equiv -1 \bmod n$.

*There exists an integer $x$ such that $x^2 \equiv -1 \bmod n$.

*$n$ is twice a product of primes congruent to $1 \bmod 4$.

*There exist integers $x, y$ such that $\gcd(x, y) = 1$ and $n = x^2 + y^2$.


Proof. $1 \Rightarrow 2$: if $n$ is even then $m^n = (m^{n/2})^2$.
$2 \Rightarrow 3$: if $x^2 \equiv -1 \bmod n$ then $x$ is either even, in which case $n$ is odd, or odd (in which case $x^2 + 1 \equiv 2 \bmod 4$, so if $n$ is even then $n \equiv 2 \bmod 4$, meaning $2$ divides $n$ but $4$ doesn't.
Now let $p$ be an odd prime divisor of $n$. It's a classic result that there exists a solution to $x^2 \equiv -1 \bmod p$ iff $p \equiv 1 \bmod 4$ and there are several ways to prove it; one is to use the fact that the group of units $\bmod p$ is cyclic of order $p-1$ and any root of $x^2 \equiv -1 \bmod p$ has multiplicative order exactly $4$.
$3 \Rightarrow 4$: by Fermat's two-square theorem (which also admits several proofs) a prime can be written in the form $x^2 + y^2$ iff $p = 2$ or $p \equiv 1 \bmod 4$, and the Brahmagupta-Fibonacci identity
$$(x^2 + y^2)(z^2 + w^2) = (xz - yw)^2 + (yz + xw)^2$$
(which again admits several proofs) shows that a product of numbers of the form $x^2 + y^2$ is again of the form $x^2 + y^2$. To show that we can always arrange for $\gcd(x, y) = 1$ is slightly more annoying but still doable. If the $\gcd$ isn't equal to $1$ then it's some product of primes congruent to $1 \bmod 4$ (note that $2$ can't appear) and each of these can be written as a sum of two (coprime) squares, which lets us use the BF identity again for each such prime, and then we can check that this operation reduces the gcd. There is a maybe somewhat more conceptual proof involving the Gaussian integers, which are hiding in the background here.
$4 \Rightarrow 3$: suppose $n = x^2 + y^2$ where $\gcd(x, y) = 1$. Then at most one of $x, y$ is even, so $x^2 + y^2 \equiv 1, 2 \bmod 4$, so if $n$ is even then it's not divisible by $4$. If $p \mid n$ then $x^2 + y^2 \equiv 0 \bmod p$, and since $\gcd(x, y) = 1$ we get that $p$ divides at most one of $x$ and $y$, from which it follows that it divides neither. Then we can divide $\bmod p$, getting
$$\left( \frac{x}{y} \right)^2 \equiv -1 \bmod p$$
so it follows as above that $p \equiv 1 \bmod 4$.
$3 \Rightarrow 1$: We're given that $n$ is twice a product of primes congruent to $1 \bmod 4$ and we want to show that there exists $m$ such that $m^n \equiv -1 \bmod n$. We'll construct a solution $\bmod p^k$ for each prime power in the prime factorization of $n$, which is enough by the Chinese remainder theorem.
First it's easy to see we can construct a solution $\bmod 2$ since $-1 \equiv 1 \bmod 2$ so we can take $m \equiv 1 \bmod 2$. Now if $p^k$ is an odd prime power factor of $n$ write $n = 2 p^k q$ where $\gcd(p, q) = 1$. We want to solve
$$m^{2 p^k q} \equiv -1 \bmod p^k.$$
To do this recall that as above, since $p \equiv 1 \bmod 4$ we know that there exists a solution to $x^2 \equiv -1 \bmod p$. By Hensel's lemma this solution lifts to a solution to $x^2 \equiv -1 \bmod p^k$. Call it $i$ (since it's a primitive $4^{th}$ root of unity). Then
$$i^{2 p^k q} \equiv (-1)^{p^k q} \equiv -1 \bmod p^k$$
since $p^k q$ is odd. So we can take $m = i$ to be our solution $\bmod p^k$. $\Box$
