Pell's Equation

Pick a whole number D that is not a perfect square — say 2, 3, or 7. Now hunt for two integers x and y that satisfy

$x^{2}$ − D·$y^{2}$ = 1.

This is Pell's equation, one of the oldest puzzles in number theory. Archimedes posed a monstrous version of it in his "cattle problem," Indian mathematicians like Brahmagupta (7th century) found ways to combine solutions, and Fermat challenged Europe with it in 1657. The name "Pell" is famously a historical misattribution by Euler — John Pell barely touched it.

The catch is the word integer. Rational answers are easy; whole-number answers are subtle. For some values of D the smallest solution is tiny, but for others it is shockingly enormous — for D = 61 the smallest y already has nine digits.

The deep surprise is this: find the one smallest solution, and you have found them all. They march out to infinity in a perfectly predictable ladder.

Choose a non-square D below. The tool runs the continued-fraction algorithm to find the fundamental (smallest) solution ($x_{1}$, $y_{1}$), then climbs the ladder: each new solution comes from the previous one by the rule

$x_{k+1} = x_1 cdot x_k + D cdot y_1 cdot y_k, y_{k+1} = x_1 cdot y_k + y_1 cdot x_k$.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>D =
    <select id="d">
      <option value="2">2</option>
      <option value="3">3</option>
      <option value="5">5</option>
      <option value="6">6</option>
      <option value="7">7</option>
      <option value="13">13</option>
      <option value="61">61</option>
    </select>
  </label>
  <button id="gen" type="button">{{btn_generate}}</button>
  <button id="more" type="button" class="ghost">{{btn_next}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<table id="tbl" class="tbl"><thead><tr><th>k</th><th>x</th><th>y</th><th>{{th_residual}}</th></tr></thead><tbody></tbody></table>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin: .4rem 0; }
label { font-weight: 600; font-size: .95rem; }
select { font: 600 14px system-ui, sans-serif; padding: .35rem .5rem; border-radius: 8px; border: 1px solid #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #0a7d33; }
.status.bad { color: #c92f3c; }
.tbl { border-collapse: collapse; width: 100%; font: 500 14px ui-monospace, monospace; }
.tbl th, .tbl td { border: 1px solid #cdd9e3; padding: .35rem .55rem; text-align: right; }
.tbl th { background: #e8eef3; color: #1d3557; }
.tbl td:first-child, .tbl th:first-child { text-align: center; width: 2.2rem; }
.tbl tr.fund td { background: #eaf6ee; font-weight: 700; }

// Code not found

Watch what happens. The first solution can be small (D = 2 gives $3^{2}$ − 2·$2^{2}$ = 1) or alarming (D = 61 gives $x_{1}$ = 1766319049). Yet once you have it, every other solution falls out by simple multiplication — no further searching. Notice the asymmetry: checking that $x^{2}$ − $Dy^{2}$ = 1 is one multiplication, but finding that first pair by brute force could take astronomically many tries.

How hard is Pell's equation, really? The answer is a happy one: it is completely solved.

• A solution always exists. For any non-square D, there are infinitely many integer solutions. Joseph-Louis Lagrange gave the first complete proof in 1768, building on Brahmagupta's chakravala method and Fermat's challenge.
• Continued fractions find it. The fundamental solution sits inside the periodic continued-fraction expansion of √D. Computing that expansion is efficient — far faster than brute-force trial of every (x, y).
• One solution generates all. The fundamental solution is the smallest unit greater than 1 in the ring ℤ[√D]; its powers (1 + √D-style products) give every other solution. This is why the demo just multiplies.
• The only catch is size. The fundamental solution can be exponentially large in D — for D = 61 it has ten digits — so the answer may be huge even though the algorithm is fast. Writing the answer down dominates the cost.

So unlike the Diophantine story in general — where Hilbert's tenth problem proved no universal algorithm can exist — this particular family is a clean success. Pell's equation is the friendly corner of number theory where everything works.

Pell's equation is far more than a curiosity:

• Best rational approximations. The solutions (x, y) make x/y an excellent approximation of √D — the convergents of the continued fraction. Ancient √2 ≈ 17/12 came from exactly this.
• Units in number fields. The fundamental solution is the fundamental unit of a real quadratic field, a cornerstone of algebraic number theory.
• Cryptanalysis. Continued-fraction methods derived from Pell's equation power Wiener's attack on RSA with small private exponents.
• Diophantine analysis. Solving related equations and proving results about integer points often reduces to a Pell-type relation.

Learn how Pell's equation is solved and you have met continued fractions — the same engine behind rational approximation, the structure of quadratic fields, and surprising attacks in cryptography. It sits close to broader Diophantine questions, but on the side that we fully understand.

Pell's equation hides a beautiful economy: find the single smallest pair of integers that works, and infinitely many more unfold from it by nothing more than multiplication. Continued fractions hand you that first pair, and Lagrange's 1768 theorem guarantees it always exists.

So while general Diophantine equations can be undecidable, Pell's stands as a reminder that some ancient puzzles end in total victory — one answer, and the rest forever after.