TAOCP 4.5.2 Exercise 16

Since $v \perp m$, the extended Euclidean algorithm yields integers $a$ and $b$ such that $av+bm=1.$ Reducing modulo $m$ gives $av\equiv 1 \pmod m,$ so $a$ is the multiplicative inverse of $v$ modulo...

taocpmathematicsalgorithmsvolume-2

Section 4.5.2: The Greatest Common Divisor

Exercise 16. [**] [M22] Design an algorithm to divide $u$ by $v$ modulo $m$, given positive integers $u$, $v$, and $m$, with $v$ relatively prime to $m$. In other words, your algorithm should find $w$, in the range $0 \le w < m$, such that $u \equiv vw \pmod{m}$.

Verified: yes
Solve time: 1m05s

Since $v \perp m$, the extended Euclidean algorithm yields integers $a$ and $b$ such that

$av+bm=1.$

Reducing modulo $m$ gives

$av\equiv 1 \pmod m,$

so $a$ is the multiplicative inverse of $v$ modulo $m$. Multiplying by $u$,

$u\equiv v(au)\pmod m.$

Therefore the required solution is

$w\equiv au\pmod m,\qquad 0\le w<m.$

An algorithm is therefore: compute $a$ and $b$ from $av+bm=1$ by the extended Euclidean algorithm; compute the least nonnegative residue of $au$ modulo $m$; output that residue as $w$. Then

$u\equiv vw\pmod m,$

and $0\le w<m$, as required.

$$ \boxed{,w=(u,v^{-1})\bmod m,} $$

where $v^{-1}$ denotes the inverse of $v$ modulo $m$.