Question

Given $n$ and $m$ are coprime, show that there exist integer $n’$ such that $nn’\bmod m=1$.
The extended Euclid’s algorithm is given below without proof, which may be useful in your proof.

Given two positive integers $m$ and $n$, we compute their greatest common divisor $d$ and two integers $a$ and $b$, such that $am+bn=d$.

$a’\leftarrow b\leftarrow 1$, $a\leftarrow b’\leftarrow 0$, $c\leftarrow m$, $d\leftarrow n$.
Let $q$ and $r$ be the quotient and remainder of $c$ divided by $d$.

We have $c=qd+r$ and $0\leq r<d$.
If $r=0$, the algorithm terminates, we have $am+bn=d$ as desired.
$c\leftarrow d$, $d\leftarrow r$, $t\leftarrow a’$, $a’\leftarrow a$, $a\leftarrow t - qa$, $t\leftarrow b’$, $b’\leftarrow b$, $b\leftarrow t-qb$

Go to E2.

This is an edited version of TAOCP vol. 1, E1.2.4, Q19.

Solution

Given $n$ and $m$ are coprime, their greatest common denominator is 1.

Algorithm E provided us a way to find $n’$ satisfying the equation $$am+n’m=1$$ where all variables are integers.

Rearrange the equation to get $$n’n=-am+1$$ it is now obvious that there exist an $n’$ such that $nn’\bmod m=1$.