lagrange-reduction-algorithm

Lagrange’s Reduction Algorithm

Summary: Lagrange’s descent procedure for deciding whether $\sqrt{a+bx+c{x}^2}$ admits a rational $x$. After reducing to the canonical form $A{p}^2+B{q}^2=z^2$ with $A,B$ square-free, one substitutes $z=nq-A{q}^{\prime }$ with $|n|\le A/2$ and $A\mid n^2-B$, obtaining a new equation with strictly smaller leading coefficient $A^{\prime }=(n^2-B)/A$. Iteration produces a strictly decreasing positive-integer sequence; termination yields either a square coefficient (success) or no valid residue (impossibility).

Sources: additions-5, additions-7

Last updated: 2026-05-10

---

Setup

Given: integers $A,B$ (square-free, after Add. V Art. 50 reductions), find rational $y$ with $A{y}^2+B$ a perfect square — equivalently, find integers $p,q,z$ with $\gcd (p,q)=1$ and

$A{p}^2+B{q}^2=z^2.$

Coprimality consequences (Add. V Art. 51): $\gcd (q,A)=1$ and $\gcd (p,B)=1$.

---

One Reduction Step

Assume $|A|>|B|$ (swap if necessary). Then

$A{p}^2=z^2-B{q}^2.$

The right side must be divisible by $A$. Apply the Add. IV Art. 48 lemma: since $\gcd (q,A)=1$, write

$z=nq-A{q}^{\prime },|n|\le A/2,n,q^{\prime }\in \mathbb{Z}.$

Substituting:

$A{p}^2=(n^2-B)q^2-2nAq{q}^{\prime }+A^2{q}^{\prime 2}.$

For divisibility by $A$, we need $A\mid n^2-B$. So we enumerate residues $n\in \{-\lfloor A/2\rfloor ,\dots ,\lfloor A/2\rfloor \}$ and keep those with $n^2\equiv B(\mathrm{mod}A)$.

For each such $n$, set

$A^{\prime }=\frac{n^2-B}{A}.$

Dividing by $A$:

$\boxed{p^2=A^{\prime }{q}^2-2nq{q}^{\prime }+A{q}^{\prime 2}.}$

---

Why $|A^{\prime }|<|A|$

$|A^{\prime }|=\frac{|n^2-B|}{|A|}.$

Since $|n|\le A/2$, we have $n^2\le A^2/4$. With $|B|<|A|$:

$|n^2-B|\le n^2+|B|\le \frac{A^2}{4}+|A|<A^2\text{(for }|A|\ge 2\text{)},$

so $|A^{\prime }|<|A|$. Strict descent.

---

Three Cases After One Step

After computing $A^{\prime }$, classify:

Case 1 — $A^{\prime }$ is a perfect square

Then $p^2=A^{\prime }{q}^2-2nq{q}^{\prime }+A{q}^{\prime 2}$ has the trivial solution $q^{\prime }=0$, $q=1$, $p=\sqrt{A^{\prime }}$. Algorithm halts in success.

Case 2 — $|A^{\prime }|<|B|$ (after stripping square factors)

Multiply the equation by $A^{\prime }$ and use $A{A}^{\prime }=n^2-B$:

$A^{\prime }{p}^2=A^{\prime 2}{q}^2-2n{A}^{\prime }q{q}^{\prime }+A{A}^{\prime }{q}^{\prime 2}=(A^{\prime }q-n{q}^{\prime }{)}^2-B{q}^{\prime 2}.$

Setting $y^{\prime }=q^{\prime }/p$, the new condition is $B{y}^{\prime 2}+A^{\prime }=\square$ — the same problem with smaller coefficients ($B$ in place of $A$, $A^{\prime }$ in place of $B$, with $|B|<|A|$ and $|A^{\prime }|<|B|$). Recurse.

Case 3 — $|A^{\prime }|\ge |B|$

Apply a second substitution within the same equation: set $q=v{q}^{\prime }+q^{\prime \prime }$ where $v$ is chosen so $|n-v{A}^{\prime }|\le A^{\prime }/2$. The new equation is

$p^2=A^{\prime }{q}^{\prime \prime 2}-2n^{\prime }{q}^{\prime \prime }{q}^{\prime }+A^{\prime \prime }{q}^{\prime 2}$

with $n^{\prime }=n-v{A}^{\prime }$ and $A^{\prime \prime }=(n^{\prime 2}-B)/A^{\prime }$, again with $|A^{\prime \prime }|<|A^{\prime }|$. Iterate until Case 1 or 2.

---

Termination by Infinite Descent

Across recursion, the leading coefficient passes through

$|A|>|A^{\prime }|>|A^{\prime \prime }|>\cdots >|B|>|C|>|D|>\cdots$

a strictly decreasing sequence of positive integers, hence finite. The algorithm halts in one of:

• Success: a square coefficient appears (Case 1) → back-substitute to recover $(p,q,z)$ and hence $y$.
• Impossibility: at some step, no $n$ in $\{-\lfloor A^{(k)}/2\rfloor ,\dots ,\lfloor A^{(k)}/2\rfloor \}$ satisfies $A^{(k)}\mid n^2-B^{(k)}$.

This is the first complete decision procedure for rational solvability of $\sqrt{a+bx+c{x}^2}$. See also infinite-descent for the proof technique.

---

Examples

Solvable: $7+15x+13x^2=\square$ (Add. V, Art. 56)

Reduces to $13y^2-139=\square$ → $13p^2-139q^2=z^2$. Swap roles ($139>13$):

Step	Equation	$A$	$B$	$n$	$A^{\prime }$	Notes
0	$-139p^2=z^2-13q^2$	$-139$	$-13$	$41$	$-12$	$41^2-13=139\cdot 12$
1	(after swap) $13r^2-12s^2=\square$	$13$	$-12$	$-$	$-$	strip $12=4\cdot 3$
1’	$13r^2-3s^2=z^{\prime 2}$	$13$	$-3$	$6$	$3$	$6^2+3=13\cdot 3$
2	$r^2=3s^2-12s{s}^{\prime }+13s^{\prime 2}$	$3$	$-3$	apply Art. 54	$1$	$\mu =2$ kills middle term
3	$r^2=3s^{\prime \prime 2}+s^{\prime 2}$	$-$	$-$	square	—	Case 1 ✓

Back-substituting gives $y=5/3$, then $x=-19/39$ or $x=-2/3$.

Impossible: $23y^2-5=\square$ (Add. V, Art. 58)

$A=23$, $B=-5$. Search residues $|n|\le 11$ with $23\mid n^2+5$: only $n=8$ works ($69=23\cdot 3$). New equation: $p^2=3q^2-16q{q}^{\prime }+23q^{\prime 2}$, $A^{\prime }=3$. Since $|3|<|-5|$, swap:

$3p^2=(3q-8q^{\prime }{)}^2+5q^{\prime 2}$ → need $-5y^{\prime 2}+3=\square$, i.e. new $A_{\text{new}}=5$, $B_{\text{new}}=3$.

Search residues $|m|\le 2$ with $5\mid m^2-3$: $m^2-3\in \{-3,-2,1\}$ for $m=0,1,2$. None divisible by 5.

Algorithm halts: $23y^2-5$ never a square.

---

Significance

Before Lagrange:

• Diophantus, Bachet, Fermat, Euler: each rationalization problem $\sqrt{a+bx+c{x}^2}$ tackled by ad-hoc tricks (the four rules of ch2.0.4-surd-rationalization).
• Impossibility: typically argued by residue-class analysis modulo small primes (e.g. ch2.0.5-impossibility-quadratic-squares) — case-by-case, no general method.

After Lagrange:

• A single algorithm decides any case in finitely many steps.
• The algorithm itself is constructive on the success side: solutions emerge via mechanical back-substitution.
• The impossibility side gains a uniform proof method: no infinite case analysis.

This is also a direct ancestor of the modern theory of reduction of binary quadratic forms developed by Gauss in the Disquisitiones Arithmeticae (1801). Lagrange’s $A,A^{\prime },A^{\prime \prime },\dots$ correspond to Gauss’s reduction-of-form coefficients along an SL₂(ℤ) orbit.

---

Specialisation in Add. VII (Integer Solvability)

For solving $x^2-A{y}^2=B$ in integers (the Add. VII problem; see add7-integer-quadratic-method), the same descent specialises as the second method of Art. 70. Starting from $C{y}^2-2nyz+B{z}^2=1$ (the auxiliary equation produced by the substitution $x=ny-Bz$), Lagrange repeatedly applies $y=m{y}^{\prime }+y^{\prime \prime }$ choosing $m$ so that the new middle coefficient $|n-m{B}^{\prime }|$ does not exceed $\frac{1}{2}{B}^{\prime }$. The transformed coefficients $n,n^{\prime },n^{\prime \prime },\dots$ form a strictly decreasing sequence of non-negative integers, so the algorithm reaches a form $L{\xi }^2-2N\xi \psi +M{\psi }^2=1\text{with}|2N|\le L,M$ in finitely many steps. Multiplying by $M$ and setting $v=M\psi -N\xi$ yields $v^2-A{\xi }^2=M$, which falls under the Add. II Art. 38 theorem.

This version has the practical advantage that the calculation depends only on $A$, not on the right side, so a single table of coefficients serves all equations $x^2-A{y}^2=B$ for the same $A$.

---

Related pages

• add5-rational-quadratic-surds — main exposition (Arts. 49–60)
• add4-integer-method-linear-y — the Art. 48 lemma that justifies $z=nq-A{q}^{\prime }$
• infinite-descent — the termination argument
• binary-quadratic-forms — Lagrange’s $P^k,Q^k$ recursion in Add. II — closely related apparatus
• ch2.0.4-surd-rationalization — Euler’s pre-Lagrange ad-hoc rules
• ch2.0.5-impossibility-quadratic-squares — Euler’s residue-class impossibility arguments
• rationalization — overview of radical elimination
• indeterminate-analysis — overarching framework
• pell-equation — close relative; Add. II proved Pell solvable using a specialized form of this descent
• add7-integer-quadratic-method — Add. VII applies this descent to the integer-solvability problem $x^2-A{y}^2=B$
• add8-pell-method-critique — counterexample showing why approximation direction matters