ch2.0.1-indeterminate-equations-first-degree

Ch2.0.1 — Of the Resolution of Equations of the First Degree with more than one Unknown Quantity

Summary: Introduces indeterminate analysis — the branch of algebra for finding integer solutions when there are fewer equations than unknowns — and develops a complete method for solving linear Diophantine equations $ax+by=c$.

Sources: chapter-2.0.1

Last updated: 2026-05-08

---

Indeterminate Questions

When a problem furnishes fewer equations than unknowns, some quantities must remain free parameters; such problems are called indeterminate. The restriction that solutions must be integer and positive (or at least rational) sharply limits the number of valid answers — sometimes finitely many, sometimes infinitely many, sometimes none. (source: chapter-2.0.1, §1–2)

Basic Method: Iterative Reduction

Given one equation in two unknowns, isolate one variable and repeatedly extract the integer part of each resulting fraction. Each step introduces a new auxiliary variable. The process terminates when a variable appears without a fractional remainder, at which point it can be chosen freely and all earlier variables determined by back-substitution. (source: chapter-2.0.1, §4–9)

Example (§4): Divide 25 into two parts, one divisible by 2 and the other by 3.

Set $2x+3y=25$. Then $x=\frac{25-3y}{2}=12-y+\frac{1-y}{2}$. For integrality, set $y-1=2z$, giving $y=2z+1$ and $x=11-3z$. Since $y<8$ we need $z\le 3$, yielding four solutions: $(x,y)=(11,1),(8,3),(5,5),(2,7)$.

Remainder Problems (Congruence Problems)

When each part must leave a given remainder upon division, represent the parts as $md+r$. This converts the problem to the same iterative technique. (source: chapter-2.0.1, §6–9)

Example (§6): Divide 100 into two parts such that the first leaves remainder 2 when divided by 5, and the second leaves remainder 4 when divided by 7. Write $5x+2$ and $7y+4$; then $5x+7y=94$ and proceed by reduction.

Euclidean-Algorithm Table (Articles 17–19)

Euler observes that the successive quotients produced by the iterative reduction are exactly the quotients of the Euclidean algorithm applied to the two coefficients $a$ and $b$ of $bp=aq+n$. This means the algebraic reduction can be bypassed entirely: run the algorithm on $a$ and $b$, copy the quotients into a parallel column of recurrences for the unknowns, and the solution structure falls out immediately. (source: chapter-2.0.1, §17–19)

Two-column table structure

The table has a left column (Euclidean steps on $a$ and $b$) and a right column (recurrences for the chain of auxiliary unknowns). Each row carries the same quotient on both sides.

Example (Article 17) — solve $20p=31q+7$. The Euclidean steps on 31 and 20, alongside the parallel unknown chain:

Euclidean step	Unknown recurrence
$31=1\times 20+11$	$p=1\times q+r$
$20=1\times 11+9$	$q=1\times r+s$
$11=1\times 9+2$	$r=1\times s+t$
$9=4\times 2+1$	$s=4\times t+u$
$2=2\times 1+0$	$t=2\times u+7$

The quotients (1, 1, 1, 4, 2) are identical on both sides. The constant $n=7$ is attached to the last equation with a $+$ sign because there are 5 rows (odd); an even number of rows would give $-7$.

Back-substitution

The last equation contains no fraction ($t=2u+7$), so $u$ may be chosen as any integer. Substituting back up the chain expresses every variable as a linear function of $u$:

$t=2u+7,s=4t+u=9u+28,r=s+t=11u+35$ $q=r+s=20u+63,p=q+r=31u+98$

Different integer values of $u$ produce the full family of solutions (the set forms an arithmetical progression).

General form (Article 19)

For $bp=aq+n$, write the Euclidean decomposition $a=Ab+c,b=Bc+d,c=Cd+e,\dots$ The right column mirrors it exactly:

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

In the final equation, attach $+n$ if the total number of rows is odd, $-n$ if even.

Simultaneous Congruences (Multi-Step Problems)

To find $N$ satisfying several congruence conditions simultaneously (e.g. $N\equiv r_1(\mathrm{mod}{m}_1)$ and $N\equiv r_2(\mathrm{mod}{m}_2)$ and $N\equiv r_3(\mathrm{mod}{m}_3)$), solve the first two, obtain $N$ as a linear function of a free parameter, then impose the third condition to produce a new Diophantine equation, and repeat. The final solutions form an arithmetical progression whose common difference is the product of the moduli. (source: chapter-2.0.1, §20–21)

Example (§21): Find $N$ with $N\equiv 3(\mathrm{mod}11)$, $N\equiv 5(\mathrm{mod}19)$, $N\equiv 10(\mathrm{mod}29)$. From the first two, $N=209u+157$; imposing the third gives $N=6061t-153458$, least positive value $N=4128$.

Impossibility Condition

The equation $bp=aq+n$ is solvable in integers if and only if $\gcd (a,b)$ divides $n$. If $\gcd (a,b)\nmid n$, the iterative reduction produces a non-integer remainder, demonstrating impossibility. When $\gcd (a,b)\mid n$, one first divides through by the common divisor to reduce to the coprime case. (source: chapter-2.0.1, §22–23)

Example (§22–23): $9p=15q+2$ is impossible because $\gcd (9,15)=3$ does not divide 2. The reduction terminates with the irresolvable expression $r=2s+\frac{2}{3}$.

Related pages

• indeterminate-analysis
• linear-diophantine-equations
• greatest-common-divisor
• arithmetical-progressions
• systems-of-linear-equations
• ch2.0.2-regula-caeci