8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please justify why $x^2-py^2=-1$ cannot have integer solutions. $\endgroup$ – rah4927 Apr 19 '14 at 12:49
  • $\begingroup$ Oh got it,we just consider the equation modulo 4. $\endgroup$ – rah4927 Apr 19 '14 at 12:51
  • $\begingroup$ @rah4927 has a solution $\endgroup$ – ziang chen Apr 19 '14 at 13:04
  • $\begingroup$ ,I don't understand your last comment. $\endgroup$ – rah4927 Apr 19 '14 at 13:17
  • 1
    $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Jun 8 '14 at 6:57
15
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can existences i or ii be found using Minkowski inequality for a suitable circle or ellipse? $\endgroup$ – cactus314 Jun 8 '14 at 21:40
  • 1
    $\begingroup$ 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). $\endgroup$ – Noam D. Elkies Jun 8 '14 at 21:50
  • 1
    $\begingroup$ 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}.$ $\endgroup$ – Geoff Robinson Jun 10 '14 at 0:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Jun 10 '14 at 18:04
  • $\begingroup$ really grateful for your solution $\endgroup$ – ziang chen Jun 13 '14 at 19:45
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Grigory M Jun 8 '14 at 11:40
  • $\begingroup$ 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. $\endgroup$ – individ Jun 8 '14 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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