MathLabs
TheoremProved

Existence of a nontrivial solution

Statement

For every positive integer dd that is not a perfect square, x2−dy2=1x^2 - d y^2 = 1 has a solution with x,yx,y positive integers.

Why is it true?

It is not obvious at all that a hyperbola x2−dy2=1x^2-dy^2=1, which certainly has real points, must pass through a lattice point — this theorem guarantees it always does, for every non-square dd, via a clever pigeonhole argument on rational approximations.

Proof sketch

By Dirichlet's approximation theorem, for any integer Q>0Q>0 there exist integers p,qp,q with 1≤q≤Q1\le q\le Q and ∣d−pq∣<1qQ\left|\sqrt d - \frac{p}{q}\right|<\frac{1}{qQ}. Letting Q→∞Q\to\infty produces infinitely many pairs (p,q)(p,q) with ∣d−pq∣<1q2\left|\sqrt d-\frac{p}{q}\right|<\frac{1}{q^2}.

For each such pair, ∣p−qd∣<1q|p-q\sqrt d|<\frac{1}{q}, so ∣p2−dq2∣=∣p−qd∣⋅∣p+qd∣<1q(2qd+1q)<2d+1|p^2-dq^2|=|p-q\sqrt d|\cdot|p+q\sqrt d|<\frac{1}{q}\left(2q\sqrt d+\frac{1}{q}\right)<2\sqrt d+1. Thus p2−dq2p^2-dq^2 takes one of only finitely many integer values in (−2d−1, 2d+1)(-2\sqrt d-1,\,2\sqrt d+1), while there are infinitely many pairs (p,q)(p,q).

By the pigeonhole principle, some fixed nonzero integer kk in that finite range satisfies p2−dq2=kp^2-dq^2=k for infinitely many pairs (p,q)(p,q). Among these infinitely many pairs, again by pigeonhole, infinitely many share the same residues p≡p0, q≡q0(mod∣k∣)p\equiv p_0,\ q\equiv q_0\pmod{|k|}.

Take two distinct such pairs (p1,q1)≠(p2,q2)(p_1,q_1)\neq(p_2,q_2) with p12−dq12=p22−dq22=kp_1^2-dq_1^2=p_2^2-dq_2^2=k and matching residues mod ∣k∣|k|. Set x+yd=(p1+q1d)(p2−q2d)kx+y\sqrt d = \frac{(p_1+q_1\sqrt d)(p_2-q_2\sqrt d)}{k}; expanding shows x=p1p2−dq1q2kx=\frac{p_1p_2-dq_1q_2}{k} and y=p1q2−p2q1ky=\frac{p_1q_2-p_2q_1}{k} are honest integers precisely because of the matching residues mod ∣k∣|k|, and multiplicativity of the norm N(a+bd)=a2−db2N(a+b\sqrt d)=a^2-db^2 gives x2−dy2=k⋅kk2=1x^2-dy^2=\frac{k\cdot k}{k^2}=1. Since (p1,q1)≠(p2,q2)(p_1,q_1)\neq(p_2,q_2) but they give the same ratio in the limit, one checks y≠0y\neq 0, and replacing (x,y)(x,y) by (∣x∣,∣y∣)(|x|,|y|) (still a solution, since only squares appear) gives a solution in positive integers.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Sean Hallgren (2007). Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem · DOI:10.1145/1206035.1206039
  2. Hendrik W. Lenstra Jr. (2002). Solving the Pell Equation