MHB Why Does Checking if 2 Divides z1 Matter in Rational Solutions for X^2+Y^2=n?

[evinda]

Hi! (Smile)

I am looking at the following exercise:

In general, the equation $X^2+Y^2=n$, when $n \equiv 3 \pmod 4$, has no rational solution.

According to my notes:

Let $x=\frac{a}{b}, y=\frac{c}{d}, a,b,c,d \in \mathbb{Z}, b \cdot d \neq 0, (a,b)=1, (c,d)=1$, solution of $X^2+Y^2=n$.

$$\frac{a^2}{b^2}+\frac{c^2}{d^2}=n \Rightarrow (ad)^2+(bc)^2=n(bd)^2$$

That means, that the equation $X^2+Y^2=n Z^2$ has an integer solution $(x_1, y_1, z_1)=(ad, bc, bd)$.

Without loss of generality, we suppose that $gcd(x_1,y_1,z_1)=1$.

If $2 \mid z_1 \Rightarrow x_1^2+y_1^2 \equiv 0 \pmod 4 \Rightarrow (2 \mid x_1 \wedge 2 \mid y_1) \Rightarrow 2 \mid (x_1,y_1,z_1)=1, \text{ Contradiction}$

Therefore, $z_1=2k+1, z_1^2 \equiv 1 \pmod 4$

$$\Rightarrow n z_1^2 \equiv n \cdot 1 \pmod 4 \equiv 3 \pmod 4$$

$$\Rightarrow x_1^2+y_1^2 \equiv 3 \pmod 4, \text{ Contradiction.}$$

Why do we check if $2 \mid z_1$ ? (Sweating)

 

[mathbalarka]

$z_1$ can either be odd or even. If even, $z_1 = 0 \pmod{2}$ and hence $z_1^2 = 0 \pmod{4}$ and $x_1^2 + y_1^2 = 0 \pmod{4}$ leading to a contradiction as above.

If $z_1$ is odd, i.e., $z_1 = 1 \pmod{2}$ then $z_1^2 = 1 \pmod{4}$ in which case $x_1^2 + y_1^2 = 3 \pmod{4}$ which also leads to a contradiction.

It's a standard method in number theory to check case-by-case modulo something and eliminate the possibilities. That's what they have done above.

 

[evinda]

$z_1$ can either be odd or even. If even, $z_1 = 0 \pmod{2}$ and hence $z_1^2 = 0 \pmod{4}$ and $x_1^2 + y_1^2 = 0 \pmod{4}$ leading to a contradiction as above.

If $z_1$ is odd, i.e., $z_1 = 1 \pmod{2}$ then $z_1^2 = 1 \pmod{4}$ in which case $x_1^2 + y_1^2 = 3 \pmod{4}$ which also leads to a contradiction.

It's a standard method in number theory to check case-by-case modulo something and eliminate the possibilities. That's what they have done above.

Ok.. but how can I know which modulo I should take?

For example, at this exercise: Show that $x^2+y^2=3$ has no rational solution, why do we check if $3 \mid x_1$ and not if $2 \mid x_1$ ? (Thinking)

 

[mathbalarka]

That completely depends on the problem you're doing. It's more or less a "trick" of number theory of some sort.

In the example $X^2 + Y^2 = 3Z^2$ (where $\text{gcd}(X, Y, Z) = 1$), considering modulo $3$ provides an obvious way to "chuck out" $Z$ from the modulo argument, giving $X^2 + Y^2 = 0 \pmod{3}$. However, this is possible if and only if $X^2 = Y^2 = 0 \pmod{3}$ (why?) in which case $X = Y = 0 \pmod{3}$. But then $X^2 + Y^2 = 0\pmod{9}$, thus $3 | Z^2 \Rightarrow 3|Z$. But then $\text{gcd}(X, Y, Z)=3 \neq 1$, contrary to our assumption.