Define well ordering property. Find the multiplicative inverse of 7 modulo 19 using Extended Euclidean Algorithm.

Well-ordering property: every non-empty set of non-negative integers has a least element. It is the basis of proofs by mathematical induction and of the division algorithm.

Inverse of 7 modulo 19

We want x such that 7x ≡ 1 (mod 19). Because gcd(7, 19) = 1, the inverse exists.

Euclidean algorithm

• 19 = 2 × 7 + 5
• 7 = 1 × 5 + 2
• 5 = 2 × 2 + 1
• 2 = 2 × 1 + 0, so gcd = 1

Work backwards (extended Euclidean algorithm)

• 1 = 5 − 2 × 2
• = 5 − 2 × (7 − 1 × 5) = 3 × 5 − 2 × 7
• = 3 × (19 − 2 × 7) − 2 × 7 = 3 × 19 − 8 × 7

So −8 × 7 ≡ 1 (mod 19), and the inverse is −8 ≡ −8 + 19 = 11.

Check: 7 × 11 = 77 = 4 × 19 + 1, so 77 ≡ 1 (mod 19). ✓