Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.