MathLabs
TheoremProved

The fundamental solution generates all solutions

Statement

If (x1,y1)(x_1,y_1) is the fundamental solution of x2−dy2=1x^2 - d y^2 = 1, then every solution in positive integers (x,y)(x,y) equals (xn,yn)(x_n,y_n) for some n≥1n\ge 1, where xn+ynd=(x1+y1d)nx_n+y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n.

Why is it true?

It says the infinitely many solutions are not a mysterious scattered set but a completely predictable geometric-like sequence generated by repeatedly "multiplying" the smallest one — reducing an infinite search to finding just one number.

Proof sketch

First check (xn,yn)(x_n,y_n) defined by xn+ynd=(x1+y1d)nx_n+y_n\sqrt d=(x_1+y_1\sqrt d)^n is indeed a solution for every nn: taking conjugates, xn−ynd=(x1−y1d)nx_n-y_n\sqrt d=(x_1-y_1\sqrt d)^n, so xn2−dyn2=(xn+ynd)(xn−ynd)=[(x1+y1d)(x1−y1d)]n=(x12−dy12)n=1n=1x_n^2-dy_n^2=(x_n+y_n\sqrt d)(x_n-y_n\sqrt d)=\left[(x_1+y_1\sqrt d)(x_1-y_1\sqrt d)\right]^n=(x_1^2-dy_1^2)^n=1^n=1.

Now suppose (x,y)(x,y) is any positive integer solution not of this form; since xn→∞x_n\to\infty as n→∞n\to\infty, there is a unique nn with xn+ynd≤x+yd<xn+1+yn+1d=(xn+ynd)(x1+y1d)x_n+y_n\sqrt d \le x+y\sqrt d < x_{n+1}+y_{n+1}\sqrt d = (x_n+y_n\sqrt d)(x_1+y_1\sqrt d).

Divide through by (xn+ynd)(x_n+y_n\sqrt d), i.e. multiply by its inverse (xn−ynd)(x_n-y_n\sqrt d) (valid since xn2−dyn2=1x_n^2-dy_n^2=1): set x′+y′d=(x+yd)(xn−ynd)x'+y'\sqrt d = (x+y\sqrt d)(x_n-y_n\sqrt d). Then 1≤x′+y′d<x1+y1d1\le x'+y'\sqrt d < x_1+y_1\sqrt d, and x′2−dy′2=(x2−dy2)(xn2−dyn2)=1⋅1=1x'^2-dy'^2=(x^2-dy^2)(x_n^2-dy_n^2)=1\cdot 1=1, so (x′,y′)(x',y') is also a solution of Pell's equation.

A short computation using x′+y′d≥1x'+y'\sqrt d\ge 1 and x′2−dy′2=1x'^2-dy'^2=1 shows x′≥1x'\ge 1 and y′≥0y'\ge 0 (a solution with x′+y′d≥1x'+y'\sqrt d\ge 1 but y′<0y'<0 would force x′>x1x'>x_1, contradicting x′+y′d<x1+y1dx'+y'\sqrt d<x_1+y_1\sqrt d combined with the norm equation). If y′>0y'>0, then (x′,y′)(x',y') is a positive solution with x′+y′d<x1+y1dx'+y'\sqrt d<x_1+y_1\sqrt d, contradicting minimality of the fundamental solution. So y′=0y'=0, forcing x′=1x'=1, i.e. x+yd=xn+yndx+y\sqrt d=x_n+y_n\sqrt d, so (x,y)=(xn,yn)(x,y)=(x_n,y_n) after all — contradicting our assumption.

Hence every positive solution is exactly some (xn,yn)(x_n,y_n), proving the fundamental solution generates the entire solution set.

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