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

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 ?

• The difference between two consecutive squares covers every odd number; this approach may be helpful in working out details for this problem. – abiessu May 24 '18 at 19:42
• 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. – abiessu May 24 '18 at 19:50
• 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... – Μάρκος Καραμέρης May 24 '18 at 20:01
• 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.$$ – Hagen von Eitzen May 24 '18 at 20:28
• 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. – Μάρκος Καραμέρης May 24 '18 at 20:36

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