모듈러 곱셈 역원

모듈러 연산은 덧셈, 빼기, 곱하기에서 분배법칙이 성립한다.
ex) $(a + b) \mod M = ((a \mod M) + (b \mod M)) \mod M$

그런데 나눗셈에선 분배법칙이 성립하지 않는다.
하지만 모듈러 곱셈 역원을 구할 수 있다면 나누기를 곱하기로 바꿔서 답을 계산할 수 있다.

즉, $(a/b)\mod M = (a*q)\mod M$ 을 만족하는 $b$의 곱셈 역원 $q$를 구해야 한다.

$b$와 $M$이 서로소일 때만 곱셈 역원이 존재할 수 있다.

1. $M$이 소수일 때,
   $q = b^{M-2} \mod M$이다.

2. $M$이 소수가 아닐 때,
   $q$는 다음 식을 만족하는 정수이다.
   $q* b+A* M \equiv 1 \ (\mod M)$

따라서 $M$과 $b$가 서로소일 때 다음이 성립한다.
$(a/b)\mod M = (a * q) \mod M$

혹은
$a/b \equiv a * q \ \ (\mod M)$

이는 페르마의 소정리를 이용한 것이다.

참고 : 구종만, 『프로그래밍 대회에서 배우는 알고리즘 문제해결 전략』 (서울:인사이트, 2012), 513-514

---

그런데 여기까지 배우고 한가지 의문이 들었다.

'$1/2 \mod 3$'처럼 정수가 아닌 수에서 모듈러 연산이 정의될 수가 있나?

결론부터 말하자면, 세간에서는
$1/2 \equiv 2 \ \ (\mod 3)$
라고 한다.

$2^{-1} \ (\mod 3)$은 "모듈러 산술(modular arithmetic)"에서 $2$와 같고,
정수 $a$에 대해 $a/2 \ \ (\mod 3)$는 계산 가능하다고 말한다.



그런데 내가 생각한 일반적인 나머지 계산은 아래와 같다.
$a \mod b=a−b⌊\frac{a}{b}⌋$

물론 $a$가 정수일 때 정의되기 때문에 $a$ 자리에 $1/2$이 들어갈 수 없지만,
굳이 $a = 1/2$ 이라고 가정하면,
$0.5 \mod 3=0.5−3⌊\frac{0.5}{3}⌋ = 0.5$ 이다.

윈도우 계산기에서 $0.5$라고 나오는 걸 보면, 이를 적용한 것 같다.

하지만 일반적인 문제에서 $a/b \ \ (\mod M)$가 정수가 아닌 유리수일 때를 계산하는 경우는 거의 없다.