[Math] Solving linear congruence (modular inverse or fraction) via gcd Bezout equation

Question

Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this site (where the extended Euclidean Algorithm is mentioned mainly) as well as looked up some books but there is no mention of this. Am I going wrong somewhere or is this a correct method of finding modular inverses? Also can't we find the Bézout's coefficients by solving the corresponding diophantine equation instead of using the extended Euclidean Algorithm?

Answer 1

Yes, it's well-known and occurs here many times, e.g. here where it is special case $\,b\! =\! 1\,$ below $\quad\ \, \exists\, x\in\Bbb Z\!:\ ax\equiv b\pmod{\! m}\!\iff\! \exists\, x,y\in\Bbb Z\!:\ ax\!+\!my = b\!\overset{\rm\ Bezout}\iff{\color{#c00}{\overbrace{\gcd(a,m)}^{\large d}}}\mid b$

Proof $\ \ (\Rightarrow)\ \ ax\equiv b\pmod{\!m}\Rightarrow ax\!+\!my = b\,$ for $\,y\in\Bbb Z\,$ so $\,\color{#c00}{d\mid a,m}\Rightarrow\,d\mid \color{#c00}ax\!+\!\color{#c00}my = b.\ $
$(\Leftarrow)\ \ $ By Bezout: $\,\exists\,\bar x,\bar y\in\Bbb Z\!:\,$ $\,a\bar x\!+\!m\bar y = d\,$ $\Rightarrow\, a(c\bar x)\!+\!\color{#0a0}m(c\bar y) = b,\,$ via scaling by $\,c = b/d,\ $ hence reducing the prior equation $\!\bmod \color{#0a0}m\,$ yields $\,a(\color{#90f}{c\bar x})\equiv b\pmod{\!\color{#0a0}m},\,$ so let $\,x=\color{#90f}{c\bar x}$.

Remark $ $ Switching back-and-forth between a linear congruence and its associated linear Diophantine equation is something so basic and ubiquitous that it is rarely explicitly mentioned - just as for use of other basic laws (associative, commutative, distributive etc.)

By the above arrows, computing modular fractions (= inverses when $\,b=1)\,$ is equivalent to solving the associated linear Diophantine equation.

There are various ways to solve such congruences and equations, e.g. see here & here for a handful of methods applicable when the solution is unique.

See here for the general method when the solution is not unique, which includes a handy fractional view of above, and its use in the extended Euclidean algorithm. As is often the case, use of fractions may yield significant simplification and conceptual insight.

See here for the equivalence of the above and CRT = Chinese Remainder Theorem.