Suppose you have integers a,b that are relatively prime to m such that
We first prove a useful lemma in working with algebraic manipulations in modular arithmetic.
Here, we take the traditional definition that .
2. Show that
By construction of the , we know that . It follow that
The last two lines of the above gives another congruence expression:
Suppose that as must be positive. Because are both relatively prime to , then by the above lemma, we know that
Likewise, we can divide out from both sides
this gives us our final congruence equivalence
Because, , the above simplifies down to .
The same logic above can be used to justify that , therefore, you can also show inductively, on the steps of the euclidean algorithm, that it preserves the properties of congruence mod m.