Solve the following congruence: 2x ≡ 7 (mod 17) Question
Solve the congruence 2x ≡ 7 (mod 17).
I have tried working out this problem but I am stuck midway. Could someone help me out by showing me or explaining how to proceed further?
Here is the work that I have so far:
Inverse of a modulo m is an integer b for which ab ≡ 1 (mod m),
a = 2
m = 17
17 = 8 ⋅ 2 + 1
2 = 2 ⋅ 1 + 0
The greatest common divisor is the last non-zero remainder values, that is, gcd (a, m) = 1.
Expressing the greatest commmon divisor as a multiple of a and m,
gcd (a, m) = 1
= 17 - 8 ⋅ 2
= 1 ⋅ 17 - 8 ⋅ 2
The inverse would then be the coefficient of a = 2, which in this case, would be -8.
And, since, -8 mod 17 = 9 , 9 is also the inverse of a modulo m.
Solving the congruence 2x ≡ 7 (mod 17) by multiplying each side by the inverse 9,
9⋅2x  ≡ 9⋅7 (mod 17)
18x ≡ 63 (mod 17)
And, this is the part where I am stuck. Could anyone help out? Thank you.
you are basically done
$18x \equiv 63 \pmod{17}$ and $18x \equiv x \pmod {17}$ and $63\equiv 12 \pmod {17}$
so $x \equiv 12 \pmod{17}$.
$7+17=24=2 \times 12$, so $x \equiv 12 \pmod{17}$.