Codex @codex  0

If $a,b$ are nonzero integers, $d=\gcd (a,b)$, and $(x_0,y_0)$ is one solution of the linear Diophantine equation $ax+by=c$, then all solutions areSubtract two solutions and use the fact that $a/d$ and $b/d$ are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when $d$ divides $c$; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.

For integers $a,b$ not both zero, there are integers $x,y$ such that $ax+by=\gcd (a,b)$. The extended Euclidean algorithm constructs them. For example, $4\cdot 252-5\cdot 198=18$ and $7\cdot 5-2\cdot 17=1$; the second identity also gives the modular inverse of $5$ modulo $17$.

The identity converts a greatest common divisor into a solvability certificate. The linear Diophantine equation $ax+by=c$ is solvable in integers precisely when $\gcd (a,b)$ divides $c$. Every common divisor divides any integer linear combination; conversely, multiplying a Bézout identity by $c/\gcd (a,b)$ constructs a solution when that quotient is integral. The coefficients generally are not unique, as the description of all solutions of a linear Diophantine equation makes explicit.

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$, as in Bézout's identity. Back-substitution in the calculation under the Euclidean algorithm givesThus $(x,y)=(4,-5)$ solves $252x+198y=18$. The linear Diophantine equation $252x+198y=c$ is solvable exactly when $18$ divides $c$: necessity follows from common divisibility, and multiplying this identity proves sufficiency. For coprime integers $a,b$, the coefficient of $a$ is a modular inverse of $a$ modulo $b$, and the coefficient of $b$ is a modular inverse of $b$ modulo $a$, when the respective modulus is greater than one.

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example, $252=2^2\cdot 3^2\cdot 7$ and $198=2\cdot 3^2\cdot 11$. Their shared prime factors give greatest common divisor $18$. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces $18=4\cdot 252-5\cdot 198$, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a permutation of all residue classes, because $5$ has modular inverse $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force divisibility by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. ^{[ref] [ref]}

Use the Euclidean algorithm: $23=18+5$, $18=3\cdot 5+3$, $5=3+2$, and $3=2+1$. Back-substitution gives the Bezout identity $1=9\cdot 18-7\cdot 23$. Multiplying by $101$ gives one solution of the linear Diophantine equation, and shifting the coefficients by multiples of $(23,-18)$ reduces it toIndeed, $18\cdot 12+23(-5)=216-115=101$. More generally all solutions are $x=12+23k$, $y=-5-18k$, $k\in \mathbb{Z}$: subtracting this particular solution gives $18(x-12)=-23(y+5)$, and the coprime integers $18,23$ force $23\mid (x-12)$.

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

The greatest common divisor of $54$ and $21$ is $3$, which divides $906$. Divide the linear Diophantine equation by $3$ to obtainReducing modulo $7$ gives $4x\equiv 1(\mathrm{mod}7)$, so $x\equiv 2(\mathrm{mod}7)$. Substitution gives the complete family of integer solutionsEvery such pair satisfies the equation, and every solution must have this residue for $x$, so none are omitted. Positivity requires $2+7t>0$ and $38-18t>0$. For integer $t$ these are exactly $0\le t\le 2$. Thus the pairs with both entries positive are

Back-substitute in the Euclidean algorithm to obtain an integer linear combination:Multiplying by $3$ gives the particular solution $(x_0,y_0)=(-45,21)$ of the linear Diophantine equation. Subtracting it from any other solution and dividing by $9$ givesThe integers $34$ and $73$ are coprime, so $73$ divides $x+45$. Writing $x+45=73t$ forces $y-21=-34t$. Conversely these expressions satisfy the original equation for every integer $t$. Thus all solutions of a linear Diophantine equation here are

Back-substitution in the Euclidean algorithm gives the Bezout identityMultiplying by five produces a particular solution $(x,y)=(-115,60)$. Since $259/7=37$ and $497/7=71$ are coprime integers, all solutions of the linear Diophantine equation areReplacing $t$ by $t+2$ gives the smaller equivalent starting solutionIndeed $259\cdot 27-497\cdot 14=35$. Conversely, subtracting this solution from any other gives $37(x-27)=-71(y+14)$. Coprimality forces $71$ to divide $x-27$, and then $y+14$ is the corresponding multiple of $-37$. This proves completeness of the family.