add3-integer-linear-equations

Additions Chapter III — Integer Solutions of First-Degree Equations

Summary: Lagrange’s third Addition gives a clean, continued-fraction-based algorithm for solving $ax-by=c$ in integers: from one solution $(\alpha ,\beta )$ all others are $(\alpha +m{b}^{\prime },\beta +m{a}^{\prime })$, and the seed solution comes from the second-to-last convergent of $b/a$. Lagrange acknowledges Bachet de Méziriac (1612/1624) as the first to solve this problem.

Sources: additions-3

Last updated: 2026-05-10

---

Position in the Additions (Appendix to Chapter I)

This chapter occupies Articles 42–45 (pp. 463–466). It is announced as an Appendix to Chapter I of the Additions — not the main text — because it builds directly on the continued-fraction theory of Add. I and the existence proof of $a^{\prime }p-b^{\prime }q=\pm 1$ in Add. II Art. 23.

The result is a constructive solution method to the problem already treated by Euler in ch2.0.1-indeterminate-equations-first-degree (the “Euclidean-table” method). Lagrange’s method is more direct and connects the linear Diophantine problem to the CF apparatus of the previous two Additions.

---

Structure of the Solution Set (Art. 42)

Setup: Solve $ax-by=c$ with $a,b,c\in \mathbb{Z}$ (any signs) for integers $x,y$.

Theorem: If $(\alpha ,\beta )$ is one integer solution, then all integer solutions are

$x=\alpha +m{b}^{\prime },y=\beta +m{a}^{\prime }$

where $m\in \mathbb{Z}$ is arbitrary and $b/a=b^{\prime }/a^{\prime }$ is the reduction to lowest terms (so $\gcd (a^{\prime },b^{\prime })=1$).

Proof: Subtracting $a\alpha -b\beta =c$ from $ax-by=c$ gives $a(x-\alpha )=b(y-\beta )$, i.e. $\frac{x-\alpha }{y-\beta }=\frac{b}{a}=\frac{b^{\prime }}{a^{\prime }}$. Since $\gcd (a^{\prime },b^{\prime })=1$ and the differences are integers, $x-\alpha =m{b}^{\prime }$ and $y-\beta =m{a}^{\prime }$ for some $m\in \mathbb{Z}$. ∎

Bound for the seed: Among the integer solutions, exactly one has $|x|\le b^{\prime }/2$, and exactly one has $|y|\le a^{\prime }/2$. So a brute-force search needs only to scan $b^{\prime }$ values of $x$ (or $a^{\prime }$ values of $y$).

---

CF-Based Direct Method (Art. 43)

Reducibility test: If $\gcd (a,b)=d$, then $d\mid c$ is necessary; otherwise no integer solution exists. Divide through by $d$ to reduce to the coprime case $a^{\prime }x-b^{\prime }y=c^{\prime }$ with $\gcd (a^{\prime },b^{\prime })=1$.

Reduction to $a^{\prime }p-b^{\prime }q=\pm 1$: If $(p,q)$ solves $a^{\prime }p-b^{\prime }q=\pm 1$, then $x=\pm p{c}^{\prime }$, $y=\pm q{c}^{\prime }$ solves $a^{\prime }x-b^{\prime }y=c^{\prime }$. Existence of $(p,q)$ is guaranteed by Add. II, Art. 23.

CF construction of $(p,q)$:

1. Reduce $b^{\prime }/a^{\prime }$ to a continued fraction $[\alpha ;\beta ,\gamma ,\dots ]$ by the Euclidean algorithm (Add. I, Art. 4).
2. Compute the principal convergents by the Add. I, Art. 10 recurrences.
3. The last convergent equals $b^{\prime }/a^{\prime }$ exactly; the second-to-last is the desired $p/q$.
4. By the cross-product identity (Add. I, Art. 12), $a^{\prime }p-b^{\prime }q=\pm 1$:
   • Upper sign ($+1$) if the rank of $b^{\prime }/a^{\prime }$ in the convergent list is even.
   • Lower sign ($-1$) if odd.

General solution: $x=\pm p{c}^{\prime }+m{b}^{\prime }$, $y=\pm q{c}^{\prime }+m{a}^{\prime }$.

Sign convention: $a,b$ may always be taken positive; flip the sign of $x$ if $a<0$, of $y$ if $b<0$.

---

Worked Example (Art. 44) — $39x-56y=11$

This is the same equation Euler treated in the main text Article 14 by his iterative-reduction method. Lagrange treats it via CFs.

$\gcd (39,56)=1$, so $a^{\prime }=39$, $b^{\prime }=56$, $c^{\prime }=11$.

Continued fraction of $56/39$ by Euclidean algorithm:

step	division	quotient
1	$56=1\cdot 39+17$	$1$
2	$39=2\cdot 17+5$	$2$
3	$17=3\cdot 5+2$	$3$
4	$5=2\cdot 2+1$	$2$
5	$2=2\cdot 1+0$	$2$

Quotients: $[1;2,3,2,2]$.

Convergents (by the $p_n=a_n{p}_{n-1}+p_{n-2}$ recurrence):

rank	1	2	3	4	5
$p$	1	3	10	23	56
$q$	1	2	7	16	39

The last convergent is $56/39=b^{\prime }/a^{\prime }$; the second-to-last is $\boxed{23/16}$, so $p=23$, $q=16$.

Sign: rank of $23/16$ is $4$ (even) → upper sign, $a^{\prime }p-b^{\prime }q=+1$.

Seed solution: $x_0=p{c}^{\prime }=23\cdot 11=253$, $y_0=q{c}^{\prime }=16\cdot 11=176$. (Verification: $39\cdot 253-56\cdot 176=9867-9856=11$. ✓)

General solution: $x=23\cdot 11+56m$, $y=16\cdot 11+39m$ for $m\in \mathbb{Z}$.

To obtain the smallest positive solution, take $m=-4$: $x=253-224=29$, $y=176-156=20$. Check: $39\cdot 29-56\cdot 20=1131-1120=11$. ✓

---

Bachet de Méziriac’s Method (Art. 45 Scholium)

Lagrange credits Bachet de Méziriac, who gave the first complete solution in the 1624 second edition of Problèmes plaisants et délectables (the 1612 first edition only announced the result).

Bachet’s recipe (essentially equivalent to the CF method, but phrased in terms of the back-substituted Euclidean remainders):

Let $c,d,e,f,\dots$ denote the successive remainders of the Euclidean algorithm on $(a,b)$, with $f=1$ being the last (when $\gcd (a,b)=1$). For an even number of remainders:

$e\mp 1=\epsilon ,\frac{\epsilon d\pm 1}{e}=\delta ,\frac{\delta c\mp 1}{d}=\gamma ,\frac{\gamma b\pm 1}{c}=\beta ,\frac{\beta a\mp 1}{b}=\alpha$

The final $\alpha ,\beta$ are the least values of $x,y$ in $ax-by=\pm 1$. For an odd number of remainders, the recipe begins $f\pm 1=\xi$ instead.

Lagrange remarks: “It is easy to see that this method is fundamentally the same as that of Chapter I; but it is less convenient because it requires divisions” (whereas the convergent recurrences only need multiplications and additions).

He also expresses regret that later mathematicians who solved the same problem ignored Bachet’s contribution — a historical aside that motivates the careful citation throughout the Additions.

---

Connection to the Main Text

Compare:

• ch2.0.1-indeterminate-equations-first-degree: Euler’s iterative reduction method (substitute $x=\frac{c+by}{a}$, isolate the integer part, descend).
• ch1.3.7-greatest-common-divisor: the Euclidean algorithm itself.

Both methods produce the same convergents in the end, but with different layouts:

• Euler’s table: tracks remainders and unknowns side by side, builds $x$ from the bottom up by back-substitution.
• Lagrange’s CF method: separates the CF expansion (Euclidean algorithm) from the convergent recurrence, then reads off $p/q$ as the last-but-one convergent.

The CF approach is cleaner pedagogically because it factors the problem: the Euclidean step gives the partial quotients, and the convergent recurrence gives the seed solution mechanically.

---

Related pages

• add1-continued-fractions — CF reduction (Art. 4) and convergent recurrences (Art. 10)
• add2-arithmetic-problems — existence of $a^{\prime }p-b^{\prime }q=\pm 1$ (Art. 23)
• continued-fractions — CF formalism
• convergents — recurrence laws and the cross-product identity
• ch2.0.1-indeterminate-equations-first-degree — Euler’s main-text method on the same problem
• linear-diophantine-equations — concept page on $ax-by=c$
• ch1.3.7-greatest-common-divisor — the Euclidean algorithm underlying CFs