Modular Multiplicative Inverse

지난번 Extended Euclid 포스팅에 이어서..
이번에는 Modular Multiplicative Inverse 에 대해서 공부해보자..

modulo 연산의 성질에서..

(a * b) mod c = ((a mod c) * (b mod c)) mod c 는 성립하지만
(a / b) mod c = ((a mod c) / (b mod c)) mod c 는 성립하지 않는다..

대신 (a / b) mod c 를 구하고자 한다면..
((a mod c) * modular_multiplicative_inverse(b, c)) mod c
이렇게 하면 되겠다..

modular multiplicative inverse 는 extended euclid 를 이용하여 구할 수 있는데..

a^(-1) = x (mod m) <-- 여기서 x 가 a 의 modular multiplicative inverse 임..
=> ax = 1 (mod m)
=> ax - 1 = qm
=> ax - mq = 1

자 이제 여기서 extended euclid 를 이용하여 x 를 구하자..~
근데 여기서 만약 gcd(a, m) <> 1 이라면 어떻게 되는거임.. -_-??