Proving The Existence And Uniqueness Of A Modular Inverse If (a, m) = 1

If \((a, m) = 1\), then there exists integers \(x\) and \(y\) such that \(ax+my=1\), which means:

$$ ax ≡ 1 \mod m $$

Here, \(x\) is the inverse. If \(ab_1 ≡ 1\) and \(ab_2 ≡ 1\), then:

$$\begin{gather} ab_1 ≡ ab_2 \mod m \\ m|a(b_1 - b_2) \end{gather}$$

Since \((m, a) = 1\):

$$ m|b_1 - b_2 ⇒ b_1 ≡ b_2 \mod m $$

This shows that the inverse is unique. By 'unique', it means there is only one solution in modulo \(m\).

Styles

(uses cookies)