Let $u$ be an integer of the form $4n+3$, where $n$ is a positive integer. Can we find integers $a$ and $b$ such that $u = a^2 + b^2$? If not, how to establish this for a fact?
-
5$\begingroup$ For any integer, $a^2 \equiv 0 \text{ or } 1 \pmod 4$. So sum of any two square $\not\equiv 3 \pmod 4$. $\endgroup$– achille huiSep 17, 2013 at 10:07
-
1$\begingroup$ achille, how to rigorously prove the first congruence? $\endgroup$– Saaqib MahmoodSep 17, 2013 at 10:28
5 Answers
Lemma 1: $a$ is odd $\Longrightarrow$ $a^2\equiv 1(\operatorname{mod} 4)$.
Proof: $a^2-1=(a-1)(a+1)$. Since $a$ is odd, both $a-1$ and $a+1$ are even, so that $a^2-1$ is divisible by $4$. $\blacksquare$
Lemma 2: $a$ is even $\Longrightarrow$ $a^2\equiv 0(\operatorname{mod} 4)$.
Proof: Trivial. $\blacksquare$
Now, suppose that $u=a^2+b^2$.
(1) If both $a$ and $b$ are even, then $u$ is divisible by four by lemma 2.
(2) If both $a$ and $b$ are odd, then $u\equiv 2(\operatorname{mod}4)$ by lemma 1.
(3) If $a$ is even and $b$ is odd (wlog), then $u\equiv1(\operatorname{mod}4)$ by lemmas 1 and 2.
That is, it is never the case that $u\equiv 3(\operatorname{mod} 4)$.
-
1
-
I'll write another argument with more group theoretic flavor in my opinion. Suppose that $p=4k+3$ is a prime number and you can write $p=x^2+y^2$. then $x^2+y^2 \equiv 0 \pmod{p} \iff x^2 \equiv -y^2 \pmod{p} \iff (xy^{-1})^2 \equiv -1 \pmod{p}$. Therefore $t=xy^{-1}$ is a solution of $x^2 \equiv -1 \pmod{p}$.
Now consider the group $\mathbb{Z}^*_p$ which consists of all non-zero residues in mod $p$ under multiplication of residues. $|G|=(4k+3)-1=4k+2$. Therefore, by a group theory result (you can also use a weaker theorem in number theory called Fermat's little theorem), for any $a \in \mathbb{Z}^*_p: a^{|G|}=1$, i.e. $a^{4k+2}=1$.
We know that there exists $x=t$ in $\mathbb{Z}^*_p$ such that $x^2 = -1$, hence, $x^4 = 1$. But this means that $\operatorname{ord}(x) \mid |G| \implies 4 \mid 4k+2$. But $4 \mid 4k$ and therefore $4 \mid 4k+2 - 4k = 2$ which is absurd. This contradiction means that it's not possible to write $p=x^2+y^2$ for $x,y \in \mathbb{Z}$.
EDIT: I should also add that any integer of the form $4k+3$ will have a prime factor of the form $4k+3$. The reason is, if none of its factors are of this form, then all of its prime factors must be of the form $4k+1$. But you can easily check that $(4k+1)(4k'+1)=4k''+1$ which leads us to a contradiction. This is how you can generalize what I said to the case when $n=4k+3$ is any natural number.
-
-
$\begingroup$ @JonasMeyer: Yes, if we don't assume $p$ is prime then it's meaningless to talk about $(\mathbb{Z}^*_p,\bar{\times})$ as a group. $\endgroup$ Sep 17, 2013 at 10:55
-
$\begingroup$ I asked because that assumption was not in the problem, but it is implicit in several places in your answer. $\endgroup$ Sep 17, 2013 at 10:58
-
$\begingroup$ @JonasMeyer: Yes, you're right. I usually use $p$ to denote a prime number, but I think it was my mistake not to mention that $p$ must be prime. I'll edit my post. $\endgroup$ Sep 17, 2013 at 10:59
For any integer n, n = 0, 1, 2 or 3 (mod 4). So $n^{2}$ = 0 or 1 (mod 4). Then for any integers a and b, $a^{2} + b^{2}$ = 0, 1 or 2 (mod 4). This means the sum of two squares can only be in the form 4k, 4k+1 or 4k+2, but never 4k+3. Thus no integer of the form 4k+3 is the sum of two squares.
No, integers of the form $4n+3$ cannot be written as a sum of two squares.
To prove this, consider $z=x^2+y^2$ modulo $4$ and you'll see that you cannot get $3$.
Let's assume x^2+y^2 = 4n+3, then either x or y has to be even. Let's assume x = 2z and write
(2z)^2+y^2 = 4n+3. This can also be written as follows:
(2z+y)^2-4zy = 4n+3 by rearrangement we can write
(2z+y)^2-1^2 =4n+2+4zy
(2z+y)^2-1^2=2(2n+2zy+1) and further
(2z+y-1)(2z+y+1)=2(2n+2zy+1)
The left side is product of two even numbers the right side is the product of even and odd number. So the assumption is wrong, and no number in the form of 4n+3 can be a sum of two squares.