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

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.

Proof

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

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

• Why can't $4uv+3u+3v+2$ be a power of $4$? – Potato Dec 9 '15 at 6:45
• That was one of the parts I was unsure about. – MathQuestion Dec 9 '15 at 6:45
• You need to justify that claim. Otherwise there's a hole in your proof. – Potato Dec 9 '15 at 6:46
• 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? – cr001 Dec 9 '15 at 7:04
• 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. – 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.

• I don't understand how a contradiction is derived, where is the fact that $p=4k+3$ is used? – cr001 Dec 9 '15 at 6:56
• I just edited the proof to use this result instead of my previous method. I believe it works now. – MathQuestion Dec 9 '15 at 6:58
• @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. – André Nicolas Dec 9 '15 at 7:13
• Oh I see, I just modified the proof. Thank you very much! – MathQuestion Dec 9 '15 at 7:23
• You are welcome. The proof works. – 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$$