I have a proof for the following problem, but I'm not sure if it's correct:

If $d\mid(4^n+1)$, show that $d$ is a sum of two squares.


$d\mid(4^n+1)\implies dm=4^n+1$, some $m\in\mathbb{Z}$.

Suppose that one of $d,m\equiv3\pmod4$. Then, $dm\equiv3\pmod4$ is not of the form $4^n+1$.

Next, suppose $d\equiv m\equiv3\pmod4$. Then $d=4u+3, m=4v+3$, some $u,v\in\mathbb{Z}\implies dm=16uv+4\cdot3u+4\cdot3v+9=4(4uv+3u+3v+2)+1$. But $4uv+3u+3v+2$ is not of the form $4^w$, hence $dm\neq4^n+1$.

Hence, we must have $d\equiv1\pmod4$, which means if a prime $p\mid d$ and $p\equiv3\pmod4$, then it occurs an even number of times in the prime factorization of $d$, so $d$ can be written as a sum of two integer squares.

Adjusted Proof

$d\mid(4^n+1)\implies dm=4^n+1$, some $m\in\mathbb{Z}$.

Let $d=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$, $p_i$ prime, $k_i\geq1$. Now suppose that some $p_i\mid d$ is congruent to $3$ mod $4$.

But then $p_i\mid4^n+1\implies 4^m=(2^m)^2\equiv-1\pmod{p_i}$, contradicting the fact that $x^2\equiv-1\pmod{p}$ has no solution for $p$ a prime, $p\equiv3\pmod4$.

Hence, we must have $d=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ with all $p_i\equiv1\pmod4$, so $d$ can be written as $d=a^2+b^2$, for some $a,b\in\mathbb{Z}$.

  • $\begingroup$ Why can't $4uv+3u+3v+2$ be a power of $4$? $\endgroup$ – Potato Dec 9 '15 at 6:45
  • $\begingroup$ That was one of the parts I was unsure about. $\endgroup$ – MathQuestion Dec 9 '15 at 6:45
  • $\begingroup$ You need to justify that claim. Otherwise there's a hole in your proof. $\endgroup$ – Potato Dec 9 '15 at 6:46
  • $\begingroup$ Is the fact $x^2\equiv-1\pmod{p}$ has no solution for $p\equiv3\pmod4$ a known theorem? Can I know the name of the theorem? $\endgroup$ – cr001 Dec 9 '15 at 7:04
  • $\begingroup$ I'm not sure if it has a name, but it follows from the properties of the Legendre symbol: $(-1/p)=1$ if $p\equiv1\pmod4$ and $(-1/p)=-1$ if $p\equiv3\pmod4$, for $p$ an odd prime. $\endgroup$ – MathQuestion Dec 9 '15 at 7:07

No proof is given for the assertion that $4uv+3u+3v+2$ is not a power of $4$.

To deal with primes $p$ of the form $4k+3$, I would note that if such a prime divides $4^n+1$, then $(2^n)^2\equiv -1\pmod{p}$, contradicting a standard result.

| cite | improve this answer | |
  • $\begingroup$ I don't understand how a contradiction is derived, where is the fact that $p=4k+3$ is used? $\endgroup$ – cr001 Dec 9 '15 at 6:56
  • $\begingroup$ I just edited the proof to use this result instead of my previous method. I believe it works now. $\endgroup$ – MathQuestion Dec 9 '15 at 6:58
  • 1
    $\begingroup$ @MathQuestion: A little change is needed, for $d$ might not be of the form $4k+3$. The crucial fact is that $d$ is not divisible by any prime of the form $4k+3$. For if such a prime $p$ divides $d$, then $p$ divides $4^n+1$, and we have shown that this is impossible. $\endgroup$ – André Nicolas Dec 9 '15 at 7:13
  • $\begingroup$ Oh I see, I just modified the proof. Thank you very much! $\endgroup$ – MathQuestion Dec 9 '15 at 7:23
  • $\begingroup$ You are welcome. The proof works. $\endgroup$ – André Nicolas Dec 9 '15 at 7:27

If $p$ is a prime divisor of $4^n+1$, then $p$ is odd and $(2^n)^2 \equiv -1\pmod{p}$. Therefore, $p \equiv 1\pmod{4}$. So if $d \mid (4^n+1)$ and $d>1$, then $d$ is a product of (not necessarily distinct) primes of the form $4k+1$. Each of these primes is a sum of two squares, and so $d$ is also a sum of two squares. On the other hand, $d=1=1^1+0^2$.

More generally, if $d \mid (a^2+b^2)$ with $\gcd(a,b)=1$, then we can again show that $d$ is a sum of two squares. For if $p$ is an odd prime divisor of $a^2+b^2$, then $b^2 \equiv -a^2\pmod{p}$ and $p \nmid ab$ (since $p \mid a$ $\Leftrightarrow$ $p \mid b$). But then $(ba^{-1})^2 \equiv -1\pmod{p}$, and again $p \equiv 1\pmod{4}$. The rest of the argument is the same as above, with the additional observation that $2=1^2+1^2$. $\blacksquare$

| cite | improve this answer | |

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.