Can an integer of the form $4n+3$ written as a sum of two squares?

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?

• For any integer, $a^2 \equiv 0 \text{ or } 1 \pmod 4$. So sum of any two square $\not\equiv 3 \pmod 4$. Sep 17, 2013 at 10:07
• achille, how to rigorously prove the first congruence? Sep 17, 2013 at 10:28

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

• triple_sec, thank you so much! Sep 17, 2013 at 10:30
• @SaaqibMahmuud My pleasure! Sep 17, 2013 at 17:29

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.

• Are you assuming that $p$ is prime? Sep 17, 2013 at 10:54
• @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. Sep 17, 2013 at 10:55
• I asked because that assumption was not in the problem, but it is implicit in several places in your answer. Sep 17, 2013 at 10:58
• @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. 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.
The text passage contains a mathematical question and multiple answers or proofs to that question. The question is about whether an integer of the form \(4n+3\) can be written as a sum of two squares. Several proofs are provided, each showing that it is not possible.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Can an integer of the form $4n+3$ written as a sum of two squares?

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?

• For any integer, $a^2 \equiv 0 \text{ or } 1 \pmod 4$. So sum of any two square $\not\equiv 3 \pmod 4$. Sep 17, 2013 at 10:07
• achille, how to rigorously prove the first congruence? Sep 17, 2013 at 10:28

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

• triple_sec, thank you so much! Sep 17, 2013 at 10:30
• @SaaqibMahmuud My pleasure! Sep 17, 2013 at 17:29

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.

• Are you assuming that $p$ is prime? Sep 17, 2013 at 10:54
• @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. Sep 17, 2013 at 10:55
• I asked because that assumption was not in the problem, but it is implicit in several places in your answer. Sep 17, 2013 at 10:58
• @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. 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.
user
The text passage contains a mathematical question and multiple answers or proofs to that question. The question is about whether an integer of the form \(4n+3\) can be written as a sum of two squares. Several proofs are provided, each showing that it is not possible.

TYPE: SINGLE_QUESTION_WITH_ANSWER