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

Question

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.

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

Answer 1

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.

Answer 2

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$