# diophantine equation $|x^2-py^2|=\frac{p-1}{2}$

Prime $p\equiv3\pmod4$, then diophantine equation

$$|x^2-py^2|=\frac{p-1}{2}$$

has a solution in integers

en, $x^2-py^2=-1$ has no solution in integers. I'd be grateful for any help you are able to provide Thanks a lot!

• Please justify why $x^2-py^2=-1$ cannot have integer solutions. – rah4927 Apr 19 '14 at 12:49
• Oh got it,we just consider the equation modulo 4. – rah4927 Apr 19 '14 at 12:51
• @rah4927 has a solution – ziang chen Apr 19 '14 at 13:04
• ,I don't understand your last comment. – rah4927 Apr 19 '14 at 13:17
• Because $-1$ is not a quadratic residue modulo $p$, then, by multiplicativity of the Legendre symbol, exactly one of $(p-1)/2$ and $-(p-1)/2$ is. The remaining task is to upgrade congruence to an equality :-) – Jyrki Lahtonen Jun 8 '14 at 6:57

This can be proved as follows:

i) $p-1$ can be written as $|a^2 - pb^2|$ for some integers $a,b$.

ii) $2$ can be written as $|a^2 - pb^2|$ for some integers $a,b$.

iii) The set of integers of the form $|a^2 - pb^2|$ is closed under multiplication. Hence by combining (i) and (ii) we find that $2(p-1)$ can be written as $|a^2 - pb^2|$ for some integers $a,b$.

iv) In (iii) the integers $a,b$ must be even. Hence we can write $a=2x$, $b=2y$ for some integers $x,y$, and then $|x^2-py^2| = 2(p-1)/4 = (p-1)/2$ as desired.

Step (i) is clear by inspection: let $a=b=1$. The proof of (ii) is given below; it is a known (though possibly not well-known) consequence of the theory of the "Pell equation". Step (iii) uses Brahmagupta's identity $$(a^2-pb^2) (c^2-pd^2) = (ac+p\,bd)^2 - p(ad+bc)^2,$$ which we now understand as multiplicativity of the norm $\| a + b \sqrt{p} \| = a^2 - pb^2$ [note that $ac+p\,bd$ and $ad+bc$ are the coefficients of $1$ and $\sqrt p$ in $(a+b\sqrt{p})(c+d\sqrt{p})$]. Step (iv) is a consequence of the familiar fact that even and odd squares are always congruent to $0$ and $1 \bmod 4$ respectively: $2(p-1)$ is a multiple of $4$, and since $p \equiv 3 \bmod 4$ the congruence $a^2 - pb^2 \equiv 0 \bmod 4$ forces $a \equiv b \equiv 0 \bmod 2$.

It remains to prove (ii). Let $(m,n)$ be a fundamental solution of $|m^2 - pn^2| = 1$. It's already been observed in the notes that reduction mod 4 proves that $m^2 - pn^2 = -1$ is not possible (one could also get this by reduction mod $p$, because $p \equiv 3 \bmod 4$ implies that the Legendre symbol $(-1/p)$ is $-1$). Therefore $m^2 - pn^2 = +1$ and $$pn^2 = m^2 - 1 = (m-1) (m+1).$$ I claim that $m$ is even. Indeed if $m$ were odd then $n$ would be even and we could write $$p(n/2)^2 = \frac{m-1}{2} \, \frac{m+1}{2}.$$ But then $(m-1)/2$ and $(m+1)/2$ would be consecutive integers whose product is $p$ times a square. Thus one of them would be a square, and the other would be $p$ times a square, giving a solution of $|a^2-pb^2| = 1$ smaller than $m^2-pn^2 = 1$; and this is impossible because $(m,n)$ was assumed fundamental.

Since $m$ is even, $m-1$ and $m+1$ are relatively prime (they differ by $2$ and are odd). Their product is $p$ times a square, so one of them is a square and the other is $p$ times a square. This gives a solution of $|x^2 - py^2| = 2$, QED.

• Can existences i or ii be found using Minkowski inequality for a suitable circle or ellipse? – cactus314 Jun 8 '14 at 21:40
• I don't think this can work in general. The Minkowski inequality isn't sensitive to primality and congruence conditions, and if $p \not \equiv 3 \bmod 4$ then the result can fail (e.g. there's no solution of either $|x^2-py^2|=2$ or $|x^2-py^2| = (p-1)/2$ for $p = 5$, or more generally $p \equiv 5 \bmod 8$ if I did this right). – Noam D. Elkies Jun 8 '14 at 21:50
• It doesn't matter much now, but it is possible to tell which sign shows up in $x^{2}-py^{2} = \pm \frac{p-1}{2}$ by looking at the congruence of $p$ (mod $8$). We know that $p \equiv 3$ (mod $4$). If $p \equiv 3$ (mod 8), then -2 is a quadratic residue (mod $p$) and hence so is $\frac{p-1}{2}$, Hence we must have $x^{2} - py^{2} = \frac{p-1}{2}.$ If $p \equiv 7$ (mod 8), then 2 is a quadratic residue (mod $p$) and hence so is $\frac{1-p}{2}$, Hence we must have $x^{2} - py^{2} = \frac{1-p}{2}.$ – Geoff Robinson Jun 10 '14 at 0:11
• Yes, I noticed this (and also that, as with $x^2 - py^2 \neq \pm 1$, it can also be proved by reduction mod $4$). It seemed neat that one can answer the OP's exact question wbout $|x^2-py^2|$ without specifying the sign, but I should mention that the sign is predictable in the next edit. – Noam D. Elkies Jun 10 '14 at 18:04
• really grateful for your solution – ziang chen Jun 13 '14 at 19:45

I would be so categorical wouldn't talk. Because there is a formula which you can write the solution of Pell equation for some simple cases.

For some Pell equations.

For special cases, there is a formula describing their solutions.

If the equation: $aX^2-qY^2=f$ rational root $\sqrt{\frac{f}{a-q}}$

Solutions can be written using the following equation Pell: $p^2-aqs^2=1$

Solutions have the form:

$Y=(2aps\pm(p^2+aqs^2))\sqrt{\frac{f}{a-q}}$

$X=(2qps\pm(p^2+aqs^2))\sqrt{\frac{f}{a-q}}$

According to these decisions can be found double this solution:

$Y_2=Y+2as(Yqs-Xp)$

$X_2=X+2p(Yqs-Xp)$

If the other root is rational: $\sqrt{\frac{f}{a}}$

Solution has the form:

$Y=2ps\sqrt{fa}$

$X=(p^2+aqs^2)\sqrt{\frac{f}{a}}$

Must take into account that the number: $p,s$ can be any character.

In our case we will use the first formula by selecting the corresponding coefficients.

• AFAICS this answer is about Pell-type equations $ax^2-qy^2=f$ s.t. either $f/(a-q)$ or $f/a$ is a square. I don't see how this helps to answer the question. – Grigory M Jun 8 '14 at 11:40
• It says that in this case there are solutions. So decision will be determined not this criterion in the problem statement. The existence of a solution is determined by other factors. – individ Jun 8 '14 at 11:43