Finding Inverse a (mod n)

먼저, 합동에서의 역이란 무엇을 말하는 것인가?

gcd(a, n) = 1이라 했을 때, s와 t를 as + nt = 1을 만족하는 정수라 하자. 유클리드 알고리즘을 이용하면 s, t를 구할 수 있다. as + nt =1은 as ≡ 1 (mod n)의 꼴로 다시 쓸 수 있으며, 이때 s를 a (mod n)에 대한 inverse라 한다.


즉, a (mod n)에 대한 inverse를 구하려면, 다음과 같은 과정을 거친다.

1. as + nt = 1을 만족하는 s, t를 유클리드 알고리즘을 이용하여 구한다.
2. inverse a ≡ s (mod n)의 결과를 얻을 수 있다.


간단히, a와 n이 간단한 수라면 유클리드 알고리즘을 사용하는 것보다 직관적으로 쉽게 알 수도 있다. 예를 들어, inverse 7 (mod 41)은 얼마인가? 즉, 어떤 수를 41로 나누었을 때 1이 남기 위한 7의 배수는 얼마인가라는 말과 동일하다.