1
$\begingroup$

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 ?

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

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

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

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'<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'<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$

$\endgroup$

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.