모듈러 연산의 경우 + - * 에 대해서 비교적 자유롭게 사용해 봤다. 아래와 같은 성질을 만족하기 때문이다.
1)(A+B)modC=((AmodC)+(BmodC))modC
2)(A−B)modC=((AmodC)−(BmodC))modC
3)(A∗B)modC=((AmodC)∗(BmodC))modC
분배 법칙과 마찬가지로 자연스럽게 생각해 왔다.
그런데 나누기의 경우는 어떻게 될까? 나누기 연산에 대한 모듈러스 연산은 잘 생각해 본적이 없다. 왜냐하면 나누기는 잘 접해보지 못한 문제이기도 하고, 나누기는 곱셈으로 변환하면 되기 때문이다.
4)(A/B)modC=(A∗B−1)modC=((AmodC)∗(B−1modC))modC
여기에서 B−1, B의 역원이 문제가 된다. 그냥 산술 그대로 수의 역원을 사용하면 되는 걸까? 당연히 그렇지 않다.
그렇다면 어떻게 구할 수 있는 걸까?
페르마의 소정리를 이용해서 구할 수 있다.
*페르마의 소정리
Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as ap ≡ a (mod p).
from wikipeia
즉 B−1≡BP−2(modP), 여기서 P는 소수
이 성질을 이용하면 많은 모듈러스 문제들을 풀 수 있다.
*모듈러 산술 연산과 합동(Congruent)은 아래 사이트를 참고한다.
https://sskl660.tistory.com/75