[수학] 나머지(Modulo) 연산 (1)

나눗셈

정수 두 개를 나누었을 때, 몫과 나머지를 구할 수 있다.

$A/B = Q\space remainder \space R$

이때 A는 피제수(dividend)라고 부른다.

B는 제수(divisor) 라고 부른다.

Q는 몫(quotient)라고 부른다.

R는 나머지(remainder)라고 부른다.

모듈러(Modulo) 연산

나머지 연산은 modulo라고 하며 mod라고 나타낸다.

$7\space mod\space 2 = 1$ 이다. 왜냐면 7을 2로 나누면 몫이 3이고 나머지가 1이므로, 이 나머지 값이 모듈러 연산의 결과값이 된다.

그렇다면 $-5\space mod\space 3$ 과 같은 경우는 어떻게 될까?

이러한 경우는 모듈러 연산의 특징을 이용해서 값을 구할 수 있다.

모듈러 연산은 피연산자의 값을 주기로 같은 결과값을 갖는 주기성을 띤다. 따라서 다음과 같은 관계가 성립한다.

$-5\space mod\space 3 = -2\space mod\space 3 = 1\space mod\space 3 = 4\space mod\space3 ...$

즉 첫번째 피연산자에 두번째 피연산자의 정수배의 값을 더해도 같은 값이 나오는 것을 이용하여 문제를 해결할 수 있다.

다시말해 -5에 3이나 6이나 9 등의 $3*K$의 값을 더해도(단 $K$는 정수) 결과값은 같다는 것이다.

모듈러 합동(Congruence Modulo)

이제 모듈러 합동(Congruence Modulo)에 대해 알아보자.

다음과 같은 수식이 있다.

$A \equiv B(modC)$

이를 A는 모듈러 C에 대해서 B와 합동이다 라고 읽는다. (A is congruent to B modulo C)

이는 다르게 말하면, $A\space mod\space C = B\space mod\space C$라는 뜻이다.

위 수식이 성립한다면, 또한 $A-B$는 $C$의 정수배라고 볼 수 있다.

모듈러 역원(Modular inverse)

역원(inverse)

역원에 대해 한번 다시 알아보자. 어떤 수와 그 수의 역원을 곱하면 1이 된다.

숫자 $A$의 역원은 $1/A$이다, 왜냐면 $A * 1/A = 1$이기 때문이다.

0보다 큰 실수는 역원을 갖는다.

그리고 $A$의 역원과 곱셈을 하는 것은 $A$로 나누는 것과 같다.

모듈러 역원(Modular inverse)

모듈러 연산은 산술적으로 나눗셈 연산이 없다. 하지만 모듈러는 역원이 존재한다.

$A \space (mod\space C)$의 역원은 $A^{-1}$ 이다.

이 때, $A*A^{-1} \equiv 1(mod\space C)$이다.

이는 달리 말하면 $A$의 역원 $A^{-1}$는 $(A*A^{-1})\space mod\space C = 1$ 를 성립하는 $A^{-1}$ 값을 뜻한다.

이때 이를 나머지 연산의 곱셈 역원이라고도 부른다.

$A^{-1}$는 정수 $A$를 $C$로 나눈 나머지 연산의 곱셈 역원이다.

이 역원은 $A$와 $C$가 서로소(coprime)인 경우에만 존재한다.

모듈러 역원의 활용

이 모듈러 역원을 어디다가 쓰는지 궁금할 수 있다. Problem Solving에서 자주쓰이는 경우는 다음과 같은 경우이다.

다음 성질이 자주 쓰인다.

$\frac A B \mod C \equiv (A \mod C) * (B^{-1} \mod C)$

프로그래밍을 할 때, $A$를 구하는 과정에서 $A$가 int나 long long 범위를 벗어나서, 온전한 $A$값을 구할 수 없고, $A \mod C$ 값만 구할 수 있는 경우

위의 성질을 활용하면 간편하다.

$A$값과 $B^{-1}$를 각각 구해서 모듈러를 취한 뒤, 곱한 뒤 다시 모듈러를 취하면 되기 때문이다.

그러면 $B^{-1}$를 어떻게 구하느냐면, 페르마의 소정리를 이용하면 된다.

-------------------------

[참고]

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/e/congruence-relation

https://www.acmicpc.net/blog/view/29