모듈러 연산 법칙

모듈러 연산의 경우 + - * 에 대해서 비교적 자유롭게 사용해 봤다. 아래와 같은 성질을 만족하기 때문이다.

$1) (A+B)\,mod\,C = ((A\,mod\,C) + (B\,mod\,C))\,mod\,C$
$2) (A-B)\,mod\,C = ((A\,mod\,C) - (B\,mod\,C))\,mod\,C$
$3) (A*B)\,mod\,C = ((A\,mod\,C) * (B\,mod\,C))\,mod\,C$

분배 법칙과 마찬가지로 자연스럽게 생각해 왔다.
그런데 나누기의 경우는 어떻게 될까? 나누기 연산에 대한 모듈러스 연산은 잘 생각해 본적이 없다. 왜냐하면 나누기는 잘 접해보지 못한 문제이기도 하고, 나누기는 곱셈으로 변환하면 되기 때문이다.

여기에서 $B^{-1}$, B의 역원이 문제가 된다. 그냥 산술 그대로 수의 역원을 사용하면 되는 걸까? 당연히 그렇지 않다.
그렇다면 어떻게 구할 수 있는 걸까?
페르마의 소정리를 이용해서 구할 수 있다.

*페르마의 소정리

Fermat's little theorem states that if p is a prime number, then for any integer a, the number $a^{p}$ − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as $a^{p}$ ≡ a (mod p).
from wikipeia

즉 $B^{-1} ≡ B^{P-2} (\,mod\, P)$, 여기서 P는 소수
이 성질을 이용하면 많은 모듈러스 문제들을 풀 수 있다.

*모듈러 산술 연산과 합동(Congruent)은 아래 사이트를 참고한다.

https://sskl660.tistory.com/75