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

  • $\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

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.