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$? – user4571 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. – user4571 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
• @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