Linear Diophantine Equations

Summary: Equations of the form $ax+by=c$ (or $ax-by=c$) to be solved in integers; Euler develops a complete iterative-reduction algorithm equivalent to the extended Euclidean algorithm, and identifies the solvability condition $\gcd (a,b)\mid c$.

Sources: chapter-2.0.1, additions-3

Last updated: 2026-05-10

---

Setup

Given integers $a,b,c>0$, find integer and positive values of $x$ and $y$ satisfying

$ax+by=c\text{or}ax-by=c$

When $b$ is negative the equation admits infinitely many solutions (free parameter); when both are positive the integer constraint limits solutions to finitely many. (source: chapter-2.0.1, §15)

Euler’s Iterative-Reduction Method

Isolate one variable, say $x=\frac{c-by}{a}$, and split off the integer part:

$x=\lfloor c/a\rfloor -\lfloor b/a\rfloor \cdot y+\frac{r-sy}{a}$

where $r,s$ are the remainders of $c$ and $b$ modulo $a$. Set $r-sy=az$ for a new integer $z$, express $y$ in terms of $z$, and repeat. The sequence of quotients is exactly the sequence produced by the Euclidean algorithm on $a$ and $b$. (source: chapter-2.0.1, §4–9)

Euclidean-Table Form (Articles 17–19)

Write the Euclidean decomposition of $a$ and $b$:

$a=Ab+c,b=Bc+d,c=Cd+e,\dots$

Build a parallel table of auxiliary variables:

$p=Aq+r,q=Br+s,r=Cs+t,\dots$

Attach the constant $n$ (with $+$ sign if the table has an odd number of rows, $-$ if even) to the last line. Back-substituting gives explicit linear formulas for $p$ and $q$ in terms of a free integer parameter. (source: chapter-2.0.1, §17–19)

Solvability Condition

$ax+by=c$ has an integer solution if and only if $\gcd (a,b)\mid c$. Euler proves this by showing the reduction terminates with an irresolvable non-integer fraction when $\gcd (a,b)\nmid c$. (source: chapter-2.0.1, §22–23)

When $\gcd (a,b)=d>1$ and $d\mid c$, divide through by $d$ to obtain $(a/d)x+(b/d)y=c/d$, now with coprime coefficients.

Solution Set Structure

If $(x_0,y_0)$ is one solution of $ax+by=c$ with $\gcd (a,b)=1$, the general solution is

$x=x_0+bt,y=y_0-at,t\in \mathbb{Z}$

The positive solutions form a finite initial segment of this arithmetic progression. (source: chapter-2.0.1, §13)

Lagrange’s CF-Based Method (Add. III)

Lagrange (Add. III, Arts. 42–45) gives an alternative route to the seed solution via continued-fractions:

1. Reduce to coprime case $a^{\prime }x-b^{\prime }y=c^{\prime }$ (divide by $\gcd$ if needed).
2. Reduce $b^{\prime }/a^{\prime }$ to a continued fraction; the second-to-last convergent $p/q$ satisfies $a^{\prime }p-b^{\prime }q=\pm 1$ (sign by parity of rank).
3. Seed solution: $x_0=\pm p{c}^{\prime }$, $y_0=\pm q{c}^{\prime }$.
4. General solution: $x=x_0+m{b}^{\prime }$, $y=y_0+m{a}^{\prime }$, $m\in \mathbb{Z}$.

This produces the same general solution as Euler’s method but factors the algorithm cleanly: the Euclidean step gives the partial quotients, and the convergent recurrence gives the seed.

Historical note (Add. III Art. 45): the first complete solution is due to Bachet de Méziriac (1624 edition of Problèmes plaisants et délectables); see add3-integer-linear-equations.

Simultaneous Congruences

To solve $N\equiv r_1(\mathrm{mod}{m}_1)$ and $N\equiv r_2(\mathrm{mod}{m}_2)$ simultaneously: write $N=m_{1}p+r_1=m_{2}q+r_2$, giving $m_{1}p-m_{2}q=r_2-r_1$, which is a linear Diophantine equation in $p$ and $q$. More congruences are handled by iterating this process; each step multiplies the period of the solution by the new modulus (the Chinese Remainder idea, though Euler does not use that name). (source: chapter-2.0.1, §13–14, §20–21)

Related pages

• indeterminate-analysis
• greatest-common-divisor
• arithmetical-progressions
• ch2.0.1-indeterminate-equations-first-degree
• add3-integer-linear-equations
• continued-fractions
• convergents