# 5 steps prove - sum of squares

I'm reading a proof and I find it very unclear. The prove contains 5 steps, and I understand each one of them. However, author didn't say how those 5 steps really justifies the theorem. Could you please have a look at these steps and give me a hand with explaining how the thesis was proven ?

Theorem

Natural number $$n$$ can be represented as sum of squares of two numbers iff in it's prime factorization, all prime divisors of the form $$p = 4m+3$$ are raised to even powers.

5 steps prove

Let's call number $$n$$ representable if and only if $$\exists_{x_0, y_0 \in \mathbb{N}_0}: n = x_0^2+y_0^2$$

Step 1

Observe that $$1, 2$$ and $$p = 4m+1$$ are representable

Step 2

If $$n_1, n_2$$ are representable then $$n_1 \cdot n_2$$ is representable.

Step 3

If $$n$$ is representable then $$nz^2, z \in \mathbb{N}$$ is representable

Step 4

If $$p = 4m+3$$ divides representable number $$n = x^2+y^2$$ then $$p$$ divides $$x$$ and $$y$$. Also $$p^2 \mid n$$

Step 5

If $$n$$ is representable and $$p = 4m+3$$ divides $$n$$ then $$p^2 \mid n$$ and $$\frac{n}{p^2}$$ is representable.

Could you please give me a hand with saying how these 5 steps actually prove thesis ?

• Step 3 looks wrong – Hagen von Eitzen Mar 27 at 17:14
• Yes - you were right. I updated my question. Thank you ! – Lucian Mar 27 at 17:19
• As a side grammar note, "prove" is a verb; "proof" is the noun you intend, I think. – Brian Tung Mar 27 at 17:40
• Thank you very much ;)) I very often mixed those two nonintentionally – Lucian Mar 27 at 17:44

## 2 Answers

$$\Leftarrow$$:

Let $$A$$ be the set of prime divisors of $$n$$ of the form $$4m+3$$, and let $$B$$ be the remaining set of prime divisiors, s.t. we can rewrite $$n$$'s prime factorization as: $$n = \prod_{a_i \in A} a_i^{e_i} \prod_{b_i \in B} b_i^{f_i} = \alpha \beta$$ where $$\alpha = \prod_{a_i \in A} a_i^{e_i}$$ and $$\beta = \prod_{b_i \in B} b_i^{f_i}$$.

Question states that all $$e_i$$ are even i.e. $$\alpha$$ is a perfect square. Then by step 3 (and using that the number $$1$$ is representable from step 1), we have $$\alpha$$ is representable. Also prime divisors of $$\beta$$ will be of the form $$4m + 1$$ and/or $$2$$. Again by step 1 and step2, $$\beta$$ is representable. Then by step 2, $$n = \alpha \beta$$ is representable.

$$\Rightarrow$$: Let $$p$$ be a prime factor of the form $$4m+3$$ which divides $$n$$. Lets' use the method of contradiction i.e. assume $$p$$'s exponent in prime factorization of $$n$$ is $$2k + 1$$. Then using step 5 repeatedly, we get that $$\frac{n}{p^2}, \frac{n}{p^4}$$ and finally $$\frac{n}{p^{2k}}$$ is representable. But then $$p$$ still divides $$\frac{n}{p^{2k}}$$, which by step 4 means that $$p^2$$ divides $$\frac{n}{p^{2k}}$$. But this means that $$p's$$ exponent in prime factorization of $$n$$ is atleast $$2k+2$$. This is a contradiction.

• Wow! That's pretty clever! Thank you for your time! – Lucian Mar 28 at 13:16

A. If $$n$$ is of the stated form, then it can be represented.

Proof. (Strong) induction on $$n$$: Let $$n$$ be of the stated form and we know that every $$n' of the stated form is representable. If $$n$$ has no prime factor at all, then $$n=1$$, which is representable according to step 1. So we may assume that $$n$$ has some prime factor $$p$$.

• If $$p\equiv 3\pmod 4$$, then in fact $$p^2\mid n$$ and so by step 3, $$n'=\frac{n}{p^2}$$ is a number of the stated form, hence is representable by induction hypothesis, and by step 3, so is $$n$$

• If $$p=2$$ or $$p\equiv 1\pmod 4$$, then $$p$$ is representable and $$n'=\frac np$$ is of the stated form, hence representable, hence by steos 1 and 2, so is $$n$$. $$\square$$

B. If $$n$$ is representable, then $$n$$ is of the stated form.

Proof. (Strong) induction again: Let $$n$$ be representable and we know that every representable $$n' is of the stated form.

If there is no $$p\equiv 3\pmod n$$ with $$p\mid n$$, then $$n$$ is of the stated form and we are done. So assume $$p\mid n$$ for some prime $$p\equiv 3\pmod 4$$. Then by step 5, $$p^2\mid n$$ and $$n'=\frac n{p^2}$$ is representable. By induction hypothesis, $$n'$$ has the stated form, but then so has $$n=p^2n'$$. $$\square$$