1
$\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$
  • 1
    $\begingroup$ Yes this is correct. Consider the equation $aa'-mb=1$ modulo $m$. $\endgroup$ – Peter Foreman Jul 12 at 8:00
  • 1
    $\begingroup$ Extended Euclidean algorithm is much faster (and simpler) to perform! $\endgroup$ – Bernard Jul 12 at 8:54
3
$\begingroup$

Yes, it's very well-known and occurs here many timees, e.g. here where it is special case $\,b = 1\,$ below

$$\rm \exists\, x\in\Bbb Z\!:\ ax\equiv b\!\!\!\pmod{\! m}\!\iff\! \exists\, x,y\in\Bbb Z\!:\ ax\!+\!my = b\!\overset{\rm\ Bezout}\iff\!\gcd(a,m)\mid b\qquad $$

Switching back-and-forth between a 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 (commutativity, associativity, etc)

By the above arrows, computing inverses is equivalant to solving the associated linear Diophatine equation.

This post explains how to solve for the above "fraction" $\,x\equiv b/a\,$ using a fractional form of the extended Euclidean algorithm (here the "fractions" are generally multi-valued). This proves very convenient for manual calculations (but be sure to master the basics before delving into more advanced topics such as modular factions)

$\endgroup$
0
$\begingroup$

Sure you can do it that way. If low enough though, you can use long division on negative numbers. and then simple remainder knowledge ex.

$$\;\; -17\\7\overline{)-121}\\\underline{-(-70)}\\\; -51\\\;\underline{-(-49)}\\\;\; -2$$

which by $-121$ being $-1$ mod $120$ and $1-(-1)=2$ implies $-17$ mod $120$ is 7's inverse multiplicatively. $-17\equiv 103\bmod 120$ is then it's least positive form.

$\endgroup$
  • 1
    $\begingroup$ The extended Euclidean (and related) algorithms do indeed use remainder calculations, which can be calculated by long division as above. However, generally such algorithms require many such remainder calculation steps, not only a single step as above. As for that particular inverse calculation, it is simpler to divide $\,120\div 7\,$ yielding $\, 120 = 7(17)+1,\,$ so $\bmod 120\!:\ 1\equiv 7(-17)\,\Rightarrow\, 7^{-1}\equiv -17\equiv 103.\,$ But how to compute remainders doesn't seem to be the primary focus of the question. $\ \ $ $\endgroup$ – Bill Dubuque Jul 12 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.