Question

Does 23^-1 (mod 1000) exist? If yes solve it.

Answer 1

Yes, 23 has an inverse mod 1000 because gcd(23, 1000) = 1 (i.e. they are coprime).

Let x be the inverse. Then x is such that

23x ≡ 1 (mod 1000)

Use the Euclidean algorithm to solve for x :

1000 = 43×23 + 11

23 = 2×11 + 1

→ 1 ≡ 23 - 2×11 (mod 1000)

→ 1 ≡ 23 - 2×(1000 - 43×23) (mod 1000)

→ 1 ≡ 23 - 2×1000 + 86×23 (mod 1000)

→ 1 ≡ 87×23 - 2×1000 ≡ 87×23 (mod 1000)

→ 23⁻¹ ≡ 87 (mod 1000)