Take the 2-minute tour ×

I'm working through a little proof of this statement, and here is an excerpt of the problem I'm following:

Suppose $p \equiv 1\pmod{4}$. Show that if $x^2-py^2=1$ the $x$ is odd and $y$ is even. Suppose that ${x_0}^2-p{y_0}^2=1$ with $y_0>0$, $y_0$ minimal. Show that $gcd(x_0+1,x_0-1)=2$. Deduce that one of two cases arises: Case 1: $x_0-1=2pu^2$, $x_0+1=2v^2$. Case 2: $x_0-1=2u^2$, $x_0+1=2pv^2$. Show that in Case 1, $v^2-pu^2=1$ with $|u|<y_0$ a contradiction to the minimality of $y_o$. show that in Case 2, $u^2-pv^2=-1$. Conclude that if $p\equiv 1\pmod{4}$ then the equation $x^2-py^2=-1$ has an integral solution.

I note that $0$ and $1$ are the only squares modulo $4$, thus $x^2$ and $y^2$ can only take values $0,1$ modulo $4$. Then mod 4, $x^2-py^2=1$ reduces to $x^2-y^2=1$, and this can only occur when $x^2\equiv 1$, $y^2\equiv 0$, and thus $x$ is odd, and $y$ is even.

Furthermore, since $x_0$ is then odd, $x_0-1$ and $x_0+1$ are both even, so their gcd is at least $2$. Also, any common divisor must divide $(x_0+1)-(x_0-1)=2$, and so the gcd is 2.

But I'm not sure why the two cases must arise, as I'm not sure what $u,v$ are. My guess is they are coprime factors of $y_0$? I'm thinking this because since $y_0$ is even, $y_0=2uv$ for some factors $u,v$ of $y_0$. Then $(x_0-1)(x_0+1)=p{y_0}^2=4pu^2v^2=(2v^2)(2pu^2)$? Is this the right train of thought? I'm not sure why it should follow that $(x_0+1),(x_0-1)$ must each be equal to one of $(2u^2),(2pv^2)$, and not some other arrangement. Is it because this is the only way to group the factors such that their products have gcd $2$? If so, I don't see why $u$ or $v$ would be coprime to $p$. Thanks for any explanation.

After this, I believe I can show the remaining steps of the problem.

share|improve this question
Is it $x^2-py^2 = 1$ or $x^2-py^2 = -1$? –  user17762 Nov 22 '10 at 1:38
Sorry, that is confusing. The problem eventually shows that from $x^2-py^2=1$ we can find a solution to $x^2-py^2=-1$ if $p\equiv 1\pmod{4}$. I will post the question in full, in hopes that it makes more sense. Thanks for pointing that out, Sivaram. –  yunone Nov 22 '10 at 1:48

1 Answer 1

up vote 3 down vote accepted

Firstly, since $(x_0+1)(x_0-1)=x_0^2-1 = py_0^2$, exactly one of $x_0+1$ and $x_0-1$ is divisible by $p$. If you take the common factor of 2 out of both of them and that factor of $p$ out of one of them, then you are left with two co-prime integers whose product is a square, therefore each must be a square by unique factorisation. The co-primality condition is crucial for that step.

So $u$ and $v$ are simply new variables that are introduced to express the fact that either both $\frac{x_0+1}{2p}$ and $\frac{x_0-1}{2}$ or both $\frac{x_0+1}{2}$ and $\frac{x_0-1}{2p}$ are squares.

share|improve this answer
Great, I see it now. Thanks Alex. –  yunone Nov 22 '10 at 2:23
You are welcome! –  Alex B. Nov 22 '10 at 2:38

Your Answer


