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?

  • $\begingroup$ 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. $\endgroup$ – Rhys Hughes Sep 18 '20 at 17:39
  • $\begingroup$ 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). $\endgroup$ – Dmitry Ezhov Sep 18 '20 at 18:42
  • 1
    $\begingroup$ 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? $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.