Can I prove that a solution of $a^2-2b^2=p$ with $1\le b<\sqrt{p}$ always exists?

Question

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 ?

Answer 1

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