3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Yes this is correct. Consider the equation $aa'-mb=1$ modulo $m$. $\endgroup$ Commented Jul 12, 2019 at 8:00
  • 3
    $\begingroup$ Extended Euclidean algorithm is much faster (and simpler) to perform! $\endgroup$
    – Bernard
    Commented Jul 12, 2019 at 8:54

2 Answers 2

6
$\begingroup$

Yes, it's well-known and occurs here many times, e.g. here where it is special case $\,b\! =\! 1\,$ below of the solvability criterion for a general linear congruence $\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(\color{darkorange}c\bar x)\!+\!\color{#0a0}m(c\bar y) = b,\,$ via scaling by $\,\color{darkorange}{c :=} \color{#c00}{b/d},\ $ hence reducing the prior equation $\!\bmod \color{#0a0}m\,$ yields $\,a(\color{darkorange}c\bar x)\equiv b\pmod{\!\color{#0a0}m},\,$ so we choose $\,x\equiv\color{darkorange}c\bar x\,$ (said in congruence language: $ $ to compute $\!\bmod m\!:\ x\equiv \color{#c48}b/a\:\!\equiv \:\!\color{#c48}{\color{darkorange}c\:\!\:\!d}/a\,$ scale $\,\bar x \equiv \color{#c00}{d}/a\,$ by $\,\color{darkorange}c)$.

Remark $ $ The special case $\,b=1\,$ above is ubiquitous, i.e. we may compute the modular inverse $\,x\equiv a^{-1}\bmod{m}\:$ by solving $\,ax+my = 1,\,$ e.g. via forward! extended Euclidean algorithm.

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.

$\endgroup$
3
  • $\begingroup$ How does one show the inverse multiple of a modulo m is unique and what exactly does it mean for it to be unique? For example solving $3x\equiv 7 \pmod{10}$ I found multiple inverses of 3 modulo 10. In fact, all of these inverses multiples satisfy the Bezout's identity given by $\gcd(3,10)=1=3s+10t$. For example, $3(7)+10(-2)=1, 3(17)+10(-5)=1, 3(27)+10(-8)=1$, and so forth. How exactly is say, $a^{-1}=7$ "unique" if $a^{-1}=17, 27, \cdots$ work just fine as well? $\endgroup$
    – Lex_i
    Commented Apr 5, 2021 at 6:19
  • $\begingroup$ I ask because in Kenneth Rosen's book on Discrete Mathmeatics and its Applications, it is claimed on section 4.4.2 that for $ax\equiv b \pmod{m}$ with $\gcd(a,m)=1$, there is a "...unique positive integer $\bar a$ less than m that is an inverse of a modulo m and every other inverse of a modulo m congruent to $\bar a$ modulo m." Proving that this is "unique" was left as an exercise. $\endgroup$
    – Lex_i
    Commented Apr 5, 2021 at 6:22
  • $\begingroup$ @Lex_i An inverse $\,a'\,$ is unique $\bmod m$ means that if $\,a'$ and $\,a''$ are inverses then $\,a'\equiv a''\pmod{m},\,$ i.e. uniqueness of roots of $\,ax\equiv 1\pmod{m}.\,$ The uniqueness proof is easy. $\endgroup$ Commented Jun 17, 2021 at 8:07
1
$\begingroup$

Yes, you can find the Bézout's coefficients without using the Euclidean algorithm.

An algorithm can be constructed by 'lifting' some algebra/logic from the Wikipedia existence proof.

Our algorithm operates on the input

$\tag 1 ax+by=z$

as follows:

If $z \mid a$ and $z \mid b$ the algorithm terminates and $\text{(1)}$ is the solution.

If $z \not\mid a$ the algorithm transforms the equation to

$\tag 2 au+bv=r, \text{ where } a = zq + r \;\text{(euclidean division)} \land \big[u = 1-qx \big] \land \big[v = -qy\big]$

and repeats with $u \text{ replacing } x$ and $v \text{ replacing } y$ and and $r \text{ replacing } z$.

If $z \not\mid b$ the algorithm transforms the equation to

$\tag 3 au+bv=r, \text{ where } b = zq + r \;\text{(euclidean division)} \land \big[u = -qx \big] \land \big[v = 1-qy\big]$

and repeats with $u \text{ replacing } x$ and $v \text{ replacing } y$ and and $r \text{ replacing } z$.

You can assume that $a \gt 0$ and initialize the input to the algorithm as the equation

$\quad a(1) + b(0) = (a) ::: a(x) + b(y) = (z)$

Observe that the algorithm iterates on $\text3{-tuples}$ until the desired form is obtained.

Example: Construct the Bézout's identity for $a = 12$ and $b=42$.

$\quad 12\,(1) + 42\,(0) = (12)$ and with $42$, $q = 3$ and $r=6$
$\quad 12\,(-3) + 42\,(1) = (6)$ and with $42$, $q = 6$ and $r=6$
$\quad 12\,(18) + 42\,(-5) = (6)$ and the algorithm stops on the Bézout's identity

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .