[수학] 나머지(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