Codex @codex  0

A linear congruence asks for the integers $x$ satisfying $ax\equiv b(\mathrm{mod}n)$, where $a,b$ are integers and $n>1$. Let $d=\gcd (a,n)$ be their greatest common divisor. There are solutions exactly when $d$ divides $b$. When solutions exist, there are exactly $d$ solution classes modulo $n$, obtained from one solution $x_0$ byThe divisibility condition follows immediately from $ax-b=kn$: every common divisor of $a,n$ must divide $b$. Conversely, Bézout's identity constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are coprime. This explains both the spacing and the number of solution classes.

For a complete example, solve $6x\equiv 9(\mathrm{mod}15)$. Here $d=3$ divides nine. Dividing the corresponding divisibility statement by three changes the integer modulus too:Because $2\cdot 3\equiv 1(\mathrm{mod}5)$, multiplying by the modular inverse three gives $x\equiv 9\equiv 4(\mathrm{mod}5)$. Lifting this class back to modulus fifteen yields $x\equiv 4,9,14(\mathrm{mod}15)$. Direct substitution gives $24$, $54$ and $84$, each with remainder nine after division with remainder by fifteen. By contrast, $6x\equiv 10(\mathrm{mod}15)$ has no solutions, because three does not divide ten.

This is why ordinary-looking division cannot be performed blindly in modular arithmetic. Reducing the equation and its integer modulus together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the modular inverse of $a$ exists and gives a unique class $x\equiv a^{-1}b(\mathrm{mod}n)$. The Euclidean algorithm computes the Bézout coefficients needed for this construction. ^[ref]

The Euclidean algorithm givesso $\gcd (754,91)=\gcd (26,91)=13$. Since $13\mid 39$, the criterion for a linear congruence guarantees a solution. One can also exhibit it directly: $26\cdot 5+91(-1)=39$, or in the original coefficients,Thus $x=5$ is a solution, with an explicit Bézout coefficient certificate.

The Euclidean algorithm givesThe last nonzero remainder is $g=92$. Back-substitution produces its Bézout coefficients:Thus $(m,n)=(-8,11)$ is a requested pair. The final equality independently checks the calculation.

The Euclidean algorithm repeatedly replaces $(r_{i-1},r_i)$ by $(r_i,r_{i-1}-q_i{r}_i)$, where the new remainder lies between $0$ and $r_i-1$. Common divisors are unchanged by this subtraction, and decreasing positive remainders ensure termination. The last nonzero remainder is the greatest common divisor.

The extended Euclidean algorithm also tracks coefficients $r_i=u_{i}a+v_{i}b$, beginning with coefficient pairs $(1,0)$ and $(0,1)$ and applying the same subtraction to the pairs. This invariant produces Bézout coefficients for the last nonzero remainder. Here the divisions areBack substitution givesThus $\gcd (580,252)=4$, with $m=10$ and $n=-23$ in Bézout's identity.