(Finding Multiplicative Inverses Modulo n; The Extended Euclidean Algorithm) Recall that e Zn has a multiplicative inverse if and only if gcd(a,n) = 1. Moreover, by Theorem 1.4, if gcd(a,n) = 1, then there exist integers r, s € Z such that ar + ns = 1. Reducing modulo n, we have that ar + ns = 1 (mod n). But ns = 0 (mod n), so ar = 1 (mod n). Therefore, we may use the Extended Euclidean Algorithm to find the numbers r and s such that ar + ns = 1, and by the above argument, (reduced modulo n) will be the multiplicative inverse of a in Zn. Using the above argument, find the multiplicative inverse of 14 € Z3.
The Correct Answer and Explanation is:
To find the multiplicative inverse of 14 in ℤ₃, we need to determine a number r such that:
14r ≡ 1 (mod 3)
This means that the product of 14 and r, when divided by 3, leaves a remainder of 1. But first, we must check whether 14 has a multiplicative inverse modulo 3. A number a has an inverse modulo n if and only if gcd(a, n) = 1.
Step 1: Check gcd(14, 3)
Since 14 and 3 are relatively prime:
gcd(14, 3) = 1
So 14 does have an inverse in ℤ₃.
Step 2: Use the Extended Euclidean Algorithm
We will find integers r and s such that:
14r + 3s = 1
Using the Euclidean Algorithm:
- 14 ÷ 3 = 4 remainder 2 → 14 = 4·3 + 2
- 3 ÷ 2 = 1 remainder 1 → 3 = 1·2 + 1
- 2 ÷ 1 = 2 remainder 0 → 2 = 2·1 + 0
So gcd is 1. Now work backwards:
From step 2:
1 = 3 − 1·2
Substitute for 2 from step 1:
1 = 3 − 1·(14 − 4·3)
= 3 − 1·14 + 4·3
= (5·3) − 1·14
So:
1 = 5·3 − 1·14
→ 1 = (−1)·14 + 5·3
Thus:
- r = −1
- s = 5
So 14·(−1) + 3·5 = 1
Step 3: Reduce r mod 3
Since r = −1, we reduce it modulo 3:
−1 mod 3 = 2
Thus, the multiplicative inverse of 14 in ℤ₃ is 2.
Final Answer:
The multiplicative inverse of 14 in ℤ₃ is 2.
Explanation:
We used the Extended Euclidean Algorithm to find integers r and s such that 14r + 3s = 1, which is equivalent to finding the inverse of 14 modulo 3. Once we found that r = −1, we reduced it modulo 3 to get 2, because −1 and 2 are congruent modulo 3. Therefore, 14·2 ≡ 1 (mod 3), which verifies that 2 is the inverse of 14 in ℤ₃.
