1. 모듈러 기본 연산
모듈러 연산은 나머지를 구한다. 파이썬에서는 산술 연산자 %와 같다. 10 mod 3 = 10 % 3 = 1. 두 수 a, b에 대해 어떤 수로 모듈러 연산을 했을 때 결과가 같다면 a, b는 모듈러 합동이라고 한다. 합동 기호를 똑같이 사용하고 예를 들어 이런 식으로 표기한다.
13 mod 4 = 1 (13을 4로 나눈 나머지는 1이고)
9 mod 4 = 1 (9를 4로 나눈 나머지도 1이다.)
13 ≡ 9 mod 4 ()
보통 0 이상의 정수에만 모듈러를 사용하는 경우가 많다. 실제로 나머지가 있는 나눗셈은 초등학교 수준의 수학에서만 다루고 있다. 하지만 괴물같은 수학자들이 이런 연산을 0 이상의 정수에만 사용하게 냅둘리가 있나. 모듈러는 음수에도 적용할 수 있다. 음수로 확장된 모듈러 연산은 모듈러 합동을 이용해 적용할 수 있다.
1 mod 3 = 1
4 mod 3 = 1
7 mod 3 = 1
...
3n+1 mod 3 = 1
위에서 나타낸 수들은 모두 모듈러 합동이다. 거꾸로 생각하면 이렇게 된다.
3n+1 mod 3 = 1
...
4 mod 3 = 1
1 mod 3 = 1
-2 mod 3 = 1
-5 mod 3 = 1
...
-3n+1 mod 3 = 1
음수 a에 대한 a mod b 는 k = a+bn > 0이 되는 n을 찾아 모듈러 합동인 k의 모듈러 값으로 구할 수 있다.
2. 역원
굳이 동물에 비유하면 기분 나쁘실 수도 있지만 개인적인 느낌이 정말 그래서 써보는 말인데, 마치 강아지들이 낯선 사람을 만나면 코부터 들이대면서 냄새를 확인하는 것처럼 수학자들은 연산자를 만나면 역원부터 찾는다. 역원에는 항등원이라는 개념이 필요하다. 어떤 수 a에 대해 연산 결과를 a로 만드는 수를 그 연산의 항등원이라고 하는데 덧셈에서는 0, 곱셈에서는 1이다. 모듈러 자체의 항등원은 존재할 수 없고, 모듈러 합과 곱의 항등원은 이렇게 정의한다.
a mod b = c
(a+p) mod b = c
p = 0
(a*q) mod b = c
q = 1
모든 실수 a에 대해 어떤 수 p를 더한 모듈러 연산이 더하기 전과 같도록 하는 p는 0이 유일하다. 그리고 모든 실수 a에 대해 어떤 수 q를 곱한 모듈러 연산이 곱하기 전과 같도록 하는 q는 1이 유일하다. 따라서 모듈러 합의 항등원은 0, 모듈러 곱의 항등원은 1이다.
역원은 어떤 수의 연산 결과로 그 연산의 항등원을 만드는 수를 말한다. 그러므로 모듈러에서의 역원은 이렇게 말할 수 있다.
a mod b = c
(a+(-a)) mod b = 0
a mod b = c
a*k mod b = 1
모듈러 합의 역원은 부호를 반전시킨 수가 되고 모듈러 곱의 역원은 연산 결과가 1이 나오는 모든 k가 된다. 예를 들어 3의 4에 대한 모듈러의 역원은 다음과 같이 구할 수 있다.
3*k mod 4 = 1
3*3 mod 4 = 9 mod 4 = 1
3*7 mod 4 = 21 mod 4 = 1
...
3. 분수의 모듈러 연산
이제 수학자 형님들의 주요 일과, 일반화다. 지금 모듈러 연산을 정수까지 확장해봤다. 이제 유리수로 확장해보자. 대학졸업한 본인의 학력에서 유리수는 두 정수 a와 b(b≠0)의 나눗셈으로 표현된다. 유리수의 모듈러를 구하기 전에 모듈러의 연산 법칙 한 가지를 알아보자.
모듈러 연산은 곱셈법칙이 적용된다.
(a*b) mod c = ((a mod c) * (b mod c)) mod c
이런 식으로 두 수의 곱의 모듈러는 모듈러 세 번으로 바꿀 수 있다. 그래서 유리수를 이렇게 표현할 수 있다.
(a÷b) mod c = (a*b^-1) mod c = ((a mod c) * (b^-1 mod c)) mod c
오 뭔가 가능성이 보이기 시작했다. 이제 b^-1의 모듈러만 계산해주면 된다. 이건 역원으로 처리할 수 있다.
b^-1*b mod c = 1 ( c > 1)
b*b^-1 mod c = 1
b*k mod c = 1
b^-1*b mod c = 1 mod c = 1 이다. 이제 b에 대한 역원 b^-1과 합동인 수 k를 찾는다. 그런데 이 경우, k를 찾을 수 없는 경우가 있다. 바로 b와 c가 공약수가 존재하는 경우다. 이 경우 k에 어떤 정수가 들어와도 역원이 될 수 없다. 따라서 k는 b와 c가 서로소인 경우에만 존재한다. 그래서 이 개념이 적용되는 문제에서는 c의 값이 1,000,000,007이나 998,244,353 같이 매우 큰 소수로 주어지는 경우가 많다.
예를 들어보는 것이 빠를 것 같다.
3/4에 대한모듈러 7을 구하는 과정이다.
3/4 mod 7
= ((3 mod 7) * (4^-1 mod 7)) mod 7
= (3 * (k mod 7)) mod 7
4^-1과 모듈러 합동인 k
4*k mod 7 = 1
k = 2, 9, ...
(3 * (2 mod 7)) mod 7
= (3 * 2) mod 7
= 6 mod 7
= 6
이게 맞아? 맞다고 함. 상세한 증명은 비 전공자에게 너무 버거워서 대충 "아 그런가보다~"하고 넘겨버렸다...
