Pell's Equation

Introduction

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.

Generate the 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">Pick a non-square <b>D</b>. The tool finds the smallest (fundamental)
solution of <b>x² − D·y² = 1</b> using continued fractions, then climbs the ladder:
each new solution is built from the first by multiplication — no more searching.</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">Find &amp; generate</button>
  <button id="more" type="button" class="ghost">+ next solution</button>
</div>
<div class="status" id="status">Choose a D and press "Find &amp; generate".</div>
<table id="tbl" class="tbl"><thead><tr><th>k</th><th>x</th><th>y</th><th>x² − D·y²</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Pell's equation x² - D y² = 1. For non-square D there are infinitely many
integer solutions (Lagrange, 1768). The fundamental (smallest) one is read
off the periodic continued fraction of √D; every other solution is a power
of it via xₖ₊₁ = x₁xₖ + D y₁yₖ,  yₖ₊₁ = x₁yₖ + y₁xₖ. We use BigInt so the
huge D=61 case (x₁ = 1766319049) stays exact. */
function fundamental(D){
  /* Continued-fraction expansion of √D; convergents h/k. First convergent with
h² - D k² = 1 is the fundamental solution. */
  const a0 = Math.floor(Math.sqrt(D));
  if(a0*a0 === D) return null; // perfect square: no solution
  let m = 0, d = 1, a = a0;
  let hPrev = 1n, h = BigInt(a0);     // numerators
  let kPrev = 0n, k = 1n;             // denominators
  const Db = BigInt(D);
  // check the 0-th convergent first (rare, but safe)
  if(h*h - Db*k*k === 1n) return { x: h, y: k };
  for(let i=0;i<2000;i++){
    m = d*a - m;
    d = (D - m*m)/d;
    a = Math.floor((a0 + m)/d);
    const hNext = BigInt(a)*h + hPrev;
    const kNext = BigInt(a)*k + kPrev;
    hPrev = h; h = hNext;
    kPrev = k; k = kNext;
    if(h*h - Db*k*k === 1n) return { x: h, y: k };
  }
  return null;
}

let D = 2, fund = null, cur = null, idx = 0;
const $ = id => document.getElementById(id);

function residual(x,y){ return x*x - BigInt(D)*y*y; }

function addRow(k,x,y){
  const tb = $('tbl').querySelector('tbody');
  const tr = document.createElement('tr');
  if(k===1) tr.className = 'fund';
  tr.innerHTML = '<td>'+k+'</td><td>'+x.toString()+'</td><td>'+y.toString()+'</td><td>'+residual(x,y).toString()+'</td>';
  tb.appendChild(tr);
}
function setStatus(t,bad){ const s=$('status'); s.textContent=t; s.className='status'+(bad?' bad':''); }

function generate(){
  D = parseInt($('d').value,10);
  $('tbl').querySelector('tbody').innerHTML='';
  fund = fundamental(D);
  if(!fund){ setStatus(fmt(`D = %D% is a perfect square — no solution.`, { D: D }), true); cur=null; return; }
  cur = { x: fund.x, y: fund.y }; idx = 1;
  addRow(1, cur.x, cur.y);
  setStatus(fmt(`Fundamental solution for D = %D%: x₁ = %x%, y₁ = %y%. Press "+ next solution".`, { D: D, x: fund.x, y: fund.y }));
  console.log(fmt(`D=%D% fundamental x1=%x% y1=%y% residual=%residual%`, { D: D, x: fund.x, y: fund.y, residual: residual(fund.x,fund.y) }));
}
function next(){
  if(!fund){ generate(); return; }
  // (xₖ₊₁, yₖ₊₁) = (x₁xₖ + D y₁yₖ, x₁yₖ + y₁xₖ)
  const Db = BigInt(D);
  const nx = fund.x*cur.x + Db*fund.y*cur.y;
  const ny = fund.x*cur.y + fund.y*cur.x;
  cur = { x: nx, y: ny }; idx++;
  addRow(idx, cur.x, cur.y);
  setStatus(fmt(`Solution #%idx% generated by one multiplication — still exact.`, { idx: idx }));
}
$('gen').addEventListener('click', generate);
$('more').addEventListener('click', next);
generate();

<p class="hint">Pick a non-square <b>D</b>. The tool finds the smallest (fundamental)
solution of <b>x² − D·y² = 1</b> using continued fractions, then climbs the ladder:
each new solution is built from the first by multiplication — no more searching.</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">Find &amp; generate</button>
  <button id="more" type="button" class="ghost">+ next solution</button>
</div>
<div class="status" id="status">Choose a D and press "Find &amp; generate".</div>
<table id="tbl" class="tbl"><thead><tr><th>k</th><th>x</th><th>y</th><th>x² − D·y²</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Pell's equation x² - D y² = 1. For non-square D there are infinitely many
integer solutions (Lagrange, 1768). The fundamental (smallest) one is read
off the periodic continued fraction of √D; every other solution is a power
of it via xₖ₊₁ = x₁xₖ + D y₁yₖ,  yₖ₊₁ = x₁yₖ + y₁xₖ. We use BigInt so the
huge D=61 case (x₁ = 1766319049) stays exact. */
function fundamental(D){
  /* Continued-fraction expansion of √D; convergents h/k. First convergent with
h² - D k² = 1 is the fundamental solution. */
  const a0 = Math.floor(Math.sqrt(D));
  if(a0*a0 === D) return null; // perfect square: no solution
  let m = 0, d = 1, a = a0;
  let hPrev = 1n, h = BigInt(a0);     // numerators
  let kPrev = 0n, k = 1n;             // denominators
  const Db = BigInt(D);
  // check the 0-th convergent first (rare, but safe)
  if(h*h - Db*k*k === 1n) return { x: h, y: k };
  for(let i=0;i<2000;i++){
    m = d*a - m;
    d = (D - m*m)/d;
    a = Math.floor((a0 + m)/d);
    const hNext = BigInt(a)*h + hPrev;
    const kNext = BigInt(a)*k + kPrev;
    hPrev = h; h = hNext;
    kPrev = k; k = kNext;
    if(h*h - Db*k*k === 1n) return { x: h, y: k };
  }
  return null;
}

let D = 2, fund = null, cur = null, idx = 0;
const $ = id => document.getElementById(id);

function residual(x,y){ return x*x - BigInt(D)*y*y; }

function addRow(k,x,y){
  const tb = $('tbl').querySelector('tbody');
  const tr = document.createElement('tr');
  if(k===1) tr.className = 'fund';
  tr.innerHTML = '<td>'+k+'</td><td>'+x.toString()+'</td><td>'+y.toString()+'</td><td>'+residual(x,y).toString()+'</td>';
  tb.appendChild(tr);
}
function setStatus(t,bad){ const s=$('status'); s.textContent=t; s.className='status'+(bad?' bad':''); }

function generate(){
  D = parseInt($('d').value,10);
  $('tbl').querySelector('tbody').innerHTML='';
  fund = fundamental(D);
  if(!fund){ setStatus(fmt(`D = %D% is a perfect square — no solution.`, { D: D }), true); cur=null; return; }
  cur = { x: fund.x, y: fund.y }; idx = 1;
  addRow(1, cur.x, cur.y);
  setStatus(fmt(`Fundamental solution for D = %D%: x₁ = %x%, y₁ = %y%. Press "+ next solution".`, { D: D, x: fund.x, y: fund.y }));
  console.log(fmt(`D=%D% fundamental x1=%x% y1=%y% residual=%residual%`, { D: D, x: fund.x, y: fund.y, residual: residual(fund.x,fund.y) }));
}
function next(){
  if(!fund){ generate(); return; }
  // (xₖ₊₁, yₖ₊₁) = (x₁xₖ + D y₁yₖ, x₁yₖ + y₁xₖ)
  const Db = BigInt(D);
  const nx = fund.x*cur.x + Db*fund.y*cur.y;
  const ny = fund.x*cur.y + fund.y*cur.x;
  cur = { x: nx, y: ny }; idx++;
  addRow(idx, cur.x, cur.y);
  setStatus(fmt(`Solution #%idx% generated by one multiplication — still exact.`, { idx: idx }));
}
$('gen').addEventListener('click', generate);
$('more').addEventListener('click', next);
generate();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pells-equation/Content licensed under CC BY-NC 4.0.

Cookies & privacy

An ancient puzzle that never runs out of answers