What is the inverse of 987x=1 (mod 11)?
What I've done so far is:
GCD(987, 11)
987 = 89 * 11 + 8
GCD(11, 8)
11 = 1 * 8 + 3
GCD(8,3)
8 = 2 * 3 + 2
GCD(3,2)
3 = 1 * 2 + 1
...So basically, the GCD(987, 11) is 1.
So...
1 = 3 - 2
= 3 - (8 - 2 * 3)
= 3 - 8 + 2 * 3
= 3 * 3 - 8
= 3 * 3 - (987 - 89 * 11)
= 3 * 3 - 987 + 89 * 11
= 3 * (11 - 8) + 89 * 11 - 987
= 3 * 11 + 89 * 11 - 3 * 8 - 987
= 92 * 11 - 3 * 8 - 897
= 92 * 11 - 3 * (987 - 89 * 11) - 987
= 359 * 11 - 4 * 987
...But everywhere I've checked says that the answer to this is 7. How is 7 even possible??
well, 987*7 = 6909 = 11*628 + 1
not sure what you mean by inverse, but x=7 is a solution to the equation.
To find the inverse of 987x ≡ 1 (mod 11), you correctly started by calculating the GCD of 987 and 11, which is 1. This means that there exists an inverse for 987 modulo 11.
You then continued the process by expressing 1 as a linear combination of 987 and 11 using the extended Euclidean algorithm. However, there appears to be an error in your calculations.
Let me guide you step by step to find the correct inverse:
Step 1: Start with the equation GCD(987, 11) = 1
Express 1 as a linear combination of 987 and 11:
1 = 3 - 2
1 = 3 - (8 - 2 * 3)
1 = 3 * 3 - 8
1 = 3 * 3 - (987 - 89 * 11)
1 = 3 * 3 - 987 + 89 * 11
1 = 3 * (11 - 8) + 89 * 11 - 987
1 = 3 * 11 + 89 * 11 - 3 * 8 - 987
1 = 92 * 11 - 3 * 8 - 987
1 = 92 * 11 - 3 * (987 - 89 * 11) - 987
1 = 359 * 11 - 4 * 987
Step 2: Now, we want to find the inverse of 987 modulo 11.
Express the inverse as: 987^-1 ≡ x (mod 11)
Step 3: From step 1, we have: 1 = 359 * 11 - 4 * 987
Step 4: Multiply both sides by 987:
987 * 1 = 987 * (359 * 11 - 4 * 987)
Simplifying:
987 ≡ 987 * 359 * 11 - 4 * 987^2 (mod 11)
987 ≡ 359 * 987 - 4 * 987^2 (mod 11)
Step 5: Rewrite 987^2 as (987 * 987):
987 ≡ 359 * 987 - 4 * (987 * 987) (mod 11)
987 ≡ 359 * 987 - 4 * (987)^2 (mod 11)
Step 6: Since 987 ≡ 0 (mod 11), we can simplify the equation:
987 ≡ -4 * (987)^2 (mod 11)
Step 7: Divide both sides by 987, keeping the equation congruent to modulo 11:
1 ≡ -4 * 987 (mod 11)
Step 8: Simplify the equation:
1 ≡ -4 * 987 ≡ 7 (mod 11)
Therefore, the inverse of 987 modulo 11 is 7.