# Primes, congruence mod4, odd exponents, sum of two squares

I am trying to prove:

(T) If a prime $p$ is congruent to $3 \bmod 4$ and it occurs with an odd exponent in the prime factorization of $n\in\mathbb N$, then $n$ is not a sum of two squares.

I have tried this idea (not sure it is going to be useful). Let $p = 4k + 3$, where $k$ is a positive integer. So $p^{2m + 1} = (4k = 3)^{2m + 1} = \overbrace{(4k + 3)^2\dots(4k + 3)^2}^m(4k + 3)$

$= \overbrace{(4t + 1)\dots(4t + 1)}^m(4k + 3)$ for some $t\in\mathbb N$

$= (4r + 1)(4k + 3)$ for some $r\in\mathbb N$

$\equiv3 \bmod 4$

I know how to prove that a sum of two squares is never equivalent to $3 \bmod 4$. So, using this fact, $p^{2m + 1}$ is not the sum of two squares.

Let $$n = \prod_{i = 1}^m {p_i}^{t_i}$$ where $p_i$ are primes and $t_i$ positive integers. Let $p = 4k + 3 = p_i$ and $t_1 = 2m + 1$. So $$n = (4r + 1)(4k + 3) \prod_{j = 1}^{i - 1} {p_j}^{t_j} \prod_{j = i + 1}^m {p_j}^{t_j}$$.

If I can prove that $n \equiv 3 \bmod 4$ I am done. However, as I said, I am not sure that this idea is going to be useful.

• Do you already know that if $p$ is a prime congruent to $3$ modulo $4$, then the congruence $x^2\equiv -1\pmod{p}$ does not have a solution? – André Nicolas Dec 17 '15 at 22:16
• @André. Thanks. No, I do not know that. How to prove that? And how to use it in the proof of (T)? – orient Dec 17 '15 at 22:22
• You can't prove $n\equiv 3\pmod{4}$, because it's wrong: there can be cases when $n$ is even. – user236182 Dec 17 '15 at 22:29
• This usually comes pretty early. If it is a group-theory oriented course, one shows that a solution of the congruence, if $p$ is an odd prime, has order $4$, and then one uses the fact that the order of an element divides the order of the group. But $4k+2$ is not divisible by $4$. In a less group theory oriented course one does something similar without mentioning groups. After that, one can show that if $p\equiv 3\pmod{4}$ and $x^2+y^2=a$ where $p$ divides $a$, then $p$ must divide $x$ and $y$. – André Nicolas Dec 17 '15 at 22:35
• @user236182: right. Sorry I missed that simple observation. – orient Dec 17 '15 at 22:57

## 1 Answer

Here is a number theory approach my teacher showed me

Let the prime factorization of $n$ be $$n=2^\alpha p_1^{\beta_1}p_2^{\beta_2}...p_r^{\beta_r}q_1^{\gamma_1}q_2^{\gamma_2}...q_s^{\gamma_s}$$ such that $p_i\equiv1 \pmod 4$ , ($1\le i \le r$) and $q_j \equiv 3 \pmod 4$ ($1\le j\le s$). Now take at least one of the $\gamma_i$ to be odd, we'll say $\gamma_1$. If $n=x^2+y^2$ and $d= \gcd(x,y)$, then with $n_1=\frac{n}{d^2}$, $x_0=\frac xd$, and $y_0 =\frac yd$ we know $$n_1=\frac n{d^2}=\left( \frac xd \right)^2 +\left( \frac yd \right)^2=x_0^2+y_0^2$$ now let $\tilde \gamma$ be the exponent of $q_1$ in the prime factorization of $n_1$. $\tilde \gamma$ is odd and $\gcd(x_0,q_1)=\gcd(y_0,q_1)=1$ so there exists an integer $a$ such that $$x_0 \equiv y_0a \pmod{q_1} \\\implies 0\equiv n_1=x_0^2+y_0^2\equiv a^2y_0^2+y_0^2\equiv y_0^2(1+a^2) \pmod{q_1}\tag1$$ $q_1$ does not divide $y_0^2$ so $$a^2+1\equiv0 \pmod{q_1} \implies a^2 \equiv -1 \pmod{q_1}$$

which cannot have a solution by Gauss' Lemma. Contradiction.

$(1)$ because if $d=\gcd(a,c)$ then the congruence $b\equiv an \pmod c$ has $d$ mutually incongruent solutions if $d \mid b$

• Thanks a lot for this. Two questions. 1) Why is $\bar\gamma$ odd? 2) Why $(x_0,q_1)=(y_0,q_1)=1\Rightarrow x_0\equiv y_0$ mod $q_1$? I do not understand your note. – orient Dec 18 '15 at 12:29
• I understand why $\bar\gamma$ is odd. I still do not get the answer to the second question. – orient Dec 18 '15 at 13:02
• @orient because their gcd is one, there is one solution to the congruence $x_0 \equiv y_0 a \pmod{q_1}$. This follows from the equivalent solutions to the linear Diophantine equation $y_0a+(-q_1)k=x_0$ if you're unfamiliar with these you can read about them here – mysatellite Dec 18 '15 at 14:41