# 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?

• Fermat's Little Theorem(s) will be of huge help to you: $$a^p\equiv a \pmod p$$ and $$a^{p-1}\equiv 1\pmod p$$ where $p$ is prime. – Rhys Hughes Sep 18 '20 at 17:39
• For $m\leq10$ and $n\leq1000$ solutions: $(m,n)$=(2,3), (2,9), (2,27), (2,81), (2,171), (2,243), (2,513), (2,729), (3,10), (3,50), (3,250), (4,5), (4,25), (4,125), (4,205), (4,625), (5,3), (5,9), (5,21), (5,26), (5,27), (5,63), (5,81), (5,147), (5,189), (5,243), (5,338), (5,441), (5,567), (5,609), (5,729), (5,903), (6,7), (6,49), (6,203), (6,343), (7,10), (7,50), (7,250), (8,3), (8,9), (8,27), (8,57), (8,81), (8,171), (8,243), (8,513), (8,729), (9,5), (9,25), (9,82), (9,125), (9,625), (10,11), (10,121), (10,253). – Dmitry Ezhov Sep 18 '20 at 18:42
• Write $n = 2r$. If there is an $m$ with $m^n + 1 \equiv 0 \pmod{n}$, then the congruence $x^2 \equiv -1 \pmod{n}$ has a solution ($x = m^r$ is one). When is $-1$ a square modulo $n$, and when can $n$ be written as the sum of two coprime squares? – Daniel Fischer Sep 18 '20 at 19:19

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:

1. There exists an integer $$m$$ such that $$m^n \equiv -1 \bmod n$$.
2. There exists an integer $$x$$ such that $$x^2 \equiv -1 \bmod n$$.
3. $$n$$ is twice a product of primes congruent to $$1 \bmod 4$$.
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$$