4
$\begingroup$

Assume, $p$ is a prime of the form $8k\pm 1$

How can I prove that the equation $$a^2-2b^2=p$$ has an integer solution with $1\le b<\sqrt{p}$ ?

I am not even sure that the claim is true, but I checked the primes upto $p=10^7$ and a solution always exists upto this limit. I tried to use that $2$ is a quadratic residue mod $p$ , but without success. Any ideas ?

$\endgroup$
  • 1
    $\begingroup$ The difference between two consecutive squares covers every odd number; this approach may be helpful in working out details for this problem. $\endgroup$ – abiessu May 24 '18 at 19:42
  • 1
    $\begingroup$ I don’t know how the problem will actually play out; I’m suggesting something that might be helpful based on my experience with squares. $\endgroup$ – abiessu May 24 '18 at 19:50
  • $\begingroup$ Notice that $p=(a+\sqrt{2}b)(a-\sqrt{2}b)$ and thus it factors in $\mathbb{Z}[\sqrt{2}]$ and is the norm of an element. Do you know the proof about $\mathbb{Z}[i]$? If so it is roughly the same. Not sure if you get a bound this way though... $\endgroup$ – Μάρκος Καραμέρης May 24 '18 at 20:01
  • 3
    $\begingroup$ Assuming there is a solution in positive integers at all, let $(a,b)$ be the solution with minimal $b$. But then $(|3a-4b|,|2a-3b|)$ is also a solution: $$ (3a-4b)^2-2(2a-3b)^2=(9a^2-24ab+16b^2) -2(4a^2-12ab+9b^2)=a^2-2b^2$$ By minimality of $b$, we conclude $|2a-3b|\ge b$, i.e., $a\ge 2b$ or $b\ge a$. The second option is clearly not compatible with $a^2-2b^2>0$, hence $a\ge 2b$ and $ 4\le\frac{a^2}{b^2}=2+\frac p{b^2}$ and ultimately $$ p\ge 2b^2. $$ $\endgroup$ – Hagen von Eitzen May 24 '18 at 20:28
  • 1
    $\begingroup$ Indeed! Let me mention that this is true because if $a+\sqrt{2}b$ is a solution then $(1-\sqrt{2})^2$ is a unit and thus: $(1-\sqrt{2})^2(a+\sqrt{2}b)$ is also a solution. $\endgroup$ – Μάρκος Καραμέρης May 24 '18 at 20:36
5
$\begingroup$

First of all, $2$ is a quadratic residue modulo $p$, since by (the supplement of) Quadratic Reciprocity $$ \left(\frac 2p\right) = \begin{cases} +1&\text{ if $p\equiv \pm1$ modulo $8$ ,}\\ -1&\text{ if $p\equiv \pm3$ modulo $8$ .} \end{cases} $$ Let $R=\Bbb Z[\sqrt 2]$ be the ring of integers in the quadratic field $\Bbb Q(\sqrt 2)$, generated by $$\sqrt 2\ ,$$ then the splitting of the ideal $(p)$ in $R$ corresponds to the structure of $R/(p)$, Prime Factorization of ideals in a Quadratic Field (wiki), and in our case $$ \Bbb Z[\sqrt 2]/p=(\Bbb Z[X]/X^2-2)/p=\Bbb Z[X]/(X^2-2,p)=(\Bbb Z[X]/p)/(X^2-2)=\Bbb F_p[X]/(X^2-2)\ , $$ which is a product of two rings, since $X^2-2$ has two different roots in $\Bbb F_p$, since $2$ is a quadratic residue modulo $p$.

The ring $R$ is factorial, unique decomposition, $p\in R$ splits as a product of two Galois conjugated factors $a\pm b\sqrt 2$, $a,b\in \Bbb Z$, so there exists a solution $$ p = (a+b\sqrt 2)(a-b\sqrt 2)=a^2 -2b^2\ .$$ Let $a,b$ be such that $a,b\ge 1$, (replace possibly $a,b$ by $\pm a$, $\pm b$ for suitable changes of signs,) and have a minimal $b$.

The units in $R$ are generated by $\pm1$, and (integer powers of) $1+\sqrt 2$. So from a solution we can get an other one by multiplying with $(\pm 1\pm \sqrt 2)$. Let us compute first: $$ (a+b\sqrt 2)(1-\sqrt 2)=(a-2b)+(b-a)\sqrt 2 \ . $$ So we can assume first $1\le b<a$. (Else, we can pass from $b$ to $b-a$.) We can even assume $b<\frac a2$. (Possibly passing from $b$ to $|b-a|=|a-b|$. This gives $$p=a^2-2b^2 >(2b)^2-2b^2=2b^2\ .$$ We found a better bound. $\blacksquare$

Note: The above "dance" is related to the (genus) theory of quadratic forms and to the question if a prime is "represented" by a given form.


Computer check, sage:

for p in primes(7, 200):
    if p%8 not in (1, 7):
        continue
    foundSolution = False    # so far
    for b in range(1, ceil(sqrt(p/2))):
        a = p + 2*b^2
        if a.is_square():
            print ( "p = %3d :: solution %3s + %s*sqrt(2) :: Is 2*%s^2 < %3s? %s"
                    % ( p, a, b, b, p, bool(2*b^2< p) ) )
            foundSolution = True
            break
    if not foundSolution:
        print "p = %s *** NO SOLUTION " % p

This gives:

p =   7 :: solution   9 + 1sqrt(2) :: Is 2*1^2 <   7? True
p =  17 :: solution  25 + 2sqrt(2) :: Is 2*2^2 <  17? True
p =  23 :: solution  25 + 1sqrt(2) :: Is 2*1^2 <  23? True
p =  31 :: solution  49 + 3sqrt(2) :: Is 2*3^2 <  31? True
p =  41 :: solution  49 + 2sqrt(2) :: Is 2*2^2 <  41? True
p =  47 :: solution  49 + 1sqrt(2) :: Is 2*1^2 <  47? True
p =  71 :: solution 121 + 5sqrt(2) :: Is 2*5^2 <  71? True
p =  73 :: solution  81 + 2sqrt(2) :: Is 2*2^2 <  73? True
p =  79 :: solution  81 + 1sqrt(2) :: Is 2*1^2 <  79? True
p =  89 :: solution 121 + 4sqrt(2) :: Is 2*4^2 <  89? True
p =  97 :: solution 169 + 6sqrt(2) :: Is 2*6^2 <  97? True
p = 103 :: solution 121 + 3sqrt(2) :: Is 2*3^2 < 103? True
p = 113 :: solution 121 + 2sqrt(2) :: Is 2*2^2 < 113? True
p = 127 :: solution 225 + 7sqrt(2) :: Is 2*7^2 < 127? True
p = 137 :: solution 169 + 4sqrt(2) :: Is 2*4^2 < 137? True
p = 151 :: solution 169 + 3sqrt(2) :: Is 2*3^2 < 151? True
p = 167 :: solution 169 + 1sqrt(2) :: Is 2*1^2 < 167? True
p = 191 :: solution 289 + 7sqrt(2) :: Is 2*7^2 < 191? True
p = 193 :: solution 225 + 4sqrt(2) :: Is 2*4^2 < 193? True
p = 199 :: solution 361 + 9sqrt(2) :: Is 2*9^2 < 199? True
$\endgroup$

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.