No Solution: y^2 = x^3 + 7

Date: 03/17/2003 at 10:53:40
From: Weijia
Subject: Congruences

Show that y^2 = x^3 + 7 has no integer solution.

I have received two hints from my professor about how to go about 
proving this, and the first is to show that if x is even, then the 
solution does not exist, and the second is that when x is odd, we can 
write x = 2z +1, and if we plug x = 2z+1 into y^2 = x^3 +7 and then 
factor out y^2 + 1 = x^3 + 8 = ( ) (), and then show that there exist 
among the factors a prime p which is congruent to 3 mod 4.

For the first part I thought if x is even then that implies y^2 is 
congruent to 7 mod 8, and that can not happen, but the second part is 
really beyond me. I have no idea how the hint is supposed to help 
me. Please enlighten me on this, Dr. Math.

Date: 03/18/2003 at 05:37:39
From: Doctor Jacques
Subject: Re: Congruences

Hi Weijia,

The first part is correct - x cannot be even.

Assume now that x is odd.

In that case, we have x^3 = x mod 4 (by Euler's theorem, as phi(4) = 2).

We have:

  y^2 = x + 7  mod 4

As x is odd, y is even, and y^2 = 0 mod 4, which shows that

  x = 1 mod 4.

We also have, as the hint suggests:

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

and x + 2 = 3 mod 4.

This means that not all the prime factors of x + 2 can be of the form 
4k + 1, as we would otherwise have x + 2 = 1 mod 4.

We have a prime factor p of x + 2 congruent to 3 mod 4.

We can write:

  y^2 + 1 = 0 mod p

and this is impossible by Gauss' Quadratic Reciprocity laws.

Does this help?  Write back if you'd like to talk about this some
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/