Proof: Uniqueness of multiplicative inverse

August 22, 2011

Prove that any multiplicative inverse i of m modulo n is unique modulo n.

Proof #

Let i and j be two multiplicative inverses of m modulo n: $im\equiv jm\equiv 1(\mathrm{mod}n)$. By the definition of congruence modulo n, $im=pn+1$ for some integer p, yielding the Bézout's identify $1=im-pn$. Since 1 clearly divides m and n, $gcd(m,n)=1$ by the Bézout's lemma. Thus, $i\equiv j\equiv 1(\mathrm{mod}n)$ by the cancellation law in modular arithmetic. Q.E.D.

• Mathematics,
• Proof