MHB Would the equation have at least one solution?

[evinda]

Hi! (Cool)

In order to show that the diophantine equation $y^2=x^3+7$ has no solution, we do the following:

If the equation would have a solution, let $(x_0,y_0)$, $y_0^2=x_0^3+7$, then $x_0$ is odd.

$$y_0^2=x_0^3+7 \Rightarrow y_0^2+1=x_0^3+8=(x_0+2)(x_0^2-2x_0+4)=(x_0+2)[(x_0-1)^2+3]$$

$(x_0-1)^2+3 \in \mathbb{N} \text{ and } (x_0-1)^2+3>1$.

It stands that $(x_0-1)^2+3 \equiv 3 \pmod{4}$.

So, $(x_0-1)^2+3$ has at least one prime divisor of the form $p \equiv 3 \pmod 4$, so:

$$(x_0-1)^2+3 \equiv 0 \pmod p, \text{ where } p \equiv 3 \pmod 4$$

$$ \Rightarrow y_0^2+1 \equiv 0 \pmod p \Rightarrow y_0^2 \equiv -1 \pmod p$$

The equation $Y^2 \equiv -1 \pmod p$ has a solution $\Leftrightarrow \left( \frac{-1}{p} \right)=1 \Leftrightarrow p \equiv 1 \pmod 4$

Therefore:

$$y_0^2 \equiv -1 \pmod p \text{ has no solution}.$$If we would conclude from this relation: $ \left ( \frac{-1}{p} \right )=1$ that $p \equiv 3 \pmod 4$, would we conclude that the diophantine equation has at least one solution? (Thinking)

 

[mathbalarka]

That is not necessary, no. Even if $-1$ was a quadratic residue modulo $p$, the equation would have been only true modulo $p$. (For example, $2 = 5$ modulo $3$, but $2 \neq 5$ in general :p)

 

[mathbalarka]

Not entirely on topic, but I'll add another proof I am familiar with.

Assume that $x$ is even. Then $x^3 = 0 \pmod{8}$. Thus $y^2 = x^3 + 7 = 7 = -1 \pmod{8}$, but this is impossible, hence $x$ is odd. Thus $x$ is either $1$ or $3$ modulo $4$.

$$y^2 + 1 = x^3 + 8 = (x + 2)(x^2 - 2x + 4)$$

$y^2 + 1$ is not divisible by any prime $3 \bmod 4$, thus the right hand side is also not divisible by any prime $3 \bmod 4$. In particular, $x + 2$ is not $3 \bmod 4$ (this is because any $3 \bmod 4$ integer must have at least one $3 \bmod 4$ prime factor) and thus is $1 \bmod 4$. Hence $x = 3 \mod 4$ in which case $x^2 - 2x + 4 = 9 - 6 + 4 = 7 = 3 \pmod{4}$ which implies there is a prime factor $p = 3 \pmod{4}$ dividing $x^2 - 2x + 4$, a contradiction $\blacksquare$

 

[evinda]

Not entirely on topic, but I'll add another proof I am familiar with.

Assume that $x$ is even. Then $x^3 = 0 \pmod{8}$. Thus $y^2 = x^3 + 7 = 7 = -1 \pmod{8}$, but this is impossible, hence $x$ is odd. Thus $x$ is either $1$ or $3$ modulo $4$.

$$y^2 + 1 = x^3 + 8 = (x + 2)(x^2 - 2x + 4)$$

$y^2 + 1$ is not divisible by any prime $3 \bmod 4$, thus the right hand side is also not divisible by any prime $3 \bmod 4$. In particular, $x + 2$ is not $3 \bmod 4$ (this is because any $3 \bmod 4$ integer must have at least one $3 \bmod 4$ prime factor) and thus is $1 \bmod 4$. Hence $x = 3 \mod 4$ in which case $x^2 - 2x + 4 = 9 - 6 + 4 = 7 = 3 \pmod{4}$ which implies there is a prime factor $p = 3 \pmod{4}$ dividing $x^2 - 2x + 4$, a contradiction $\blacksquare$

We know that $x$ is odd, so it is of the form $2k+1$.

Therefore:

$$x+2=2k+1+2=2k+3$$

• $k=2m+1: x+2=2(2m+1)+3=4m+5 \equiv 1 \pmod 4 \Rightarrow x \equiv 3 \pmod 4$
• $ k=2m: x+2=4m+3 \equiv 3 \pmod 4 \Rightarrow x \equiv 1 \pmod 4$

How do we conclude that $x \equiv 3 \pmod 4$ ? (Thinking)

 

[mathbalarka]

How do we conclude that $x \equiv 3 \pmod 4$ ?(Thinking)

Right, so you have (correctly (Yes)) concluded that $x$ is either $1$ or $3$ modulo $4$.

Now, assume $x = 1 \pmod 4$. Then $x + 2 = 3 \pmod 4$. In that case, $y^2 + 1$ is divisible by some number $3 \pmod 4$. The fact I have used for contradiction is

Claim : Any integer of the form $a^2 + b^2$ is not divisible by any integer $n$ of the form 3 mod 4.

Can you try to prove this claim?