Modular Arithmetic

Modular Arithmetic

---

정수 \(a, b, m\)에 대하여, \(m \ | \ (a-b)\) 일때, \(a\)는 법 \(m\)에 대하여 \(b\)와 합동이다(\(a\) is congruent to \(b\) modulo \(m\)). 이때, 기호로 \(a\equiv b\pmod m\)이라고 쓴다. 여기서 \(m\)을 합동의 법(modular)이라고 한다. 수학적인 정의는 이렇고, 간단하게 말하면 '\(a\)와 \(b\)를 \(m\)으로 나누었을 때, 그 둘의 나머지가 같다'라고 생각하면 된다.

모듈라 연산에서의 덧셈, 뺄셈, 곱셈은 다음과 같은 성질들이 성립한다.

\((a+b) \pmod m \equiv ((a \pmod m) + (b \pmod m)) \pmod m\)

\((a-b) \pmod m \equiv ((a \pmod m) - (b \pmod m)) \pmod m\)

\((a \times b) \pmod m \equiv ((a \pmod m) \times (b \pmod m)) \pmod m\)

그러나 위의 덧셈, 뺄셈, 곱셈과는 다르게 나눗셈에서는 이와 같은 식으로 계산할 수 없다. 모듈라 나눗셈에서는 \(b\)로 나누는 대신 \(b\)의 곱셈 역원(multiplicative inverse)을 곱한다. 여기서 모듈라 곱셈 역원이란 \(b \times b^{-1} \equiv 1 \pmod m\)을 만족하는 \(b^{-1}\)을 말한다. \(b\)의 곱셈 역원은 항상 존재하는 것이 아니라, \(b\)와 \(m\)이 서로소인 경우에만 존재한다. 만약 이러한 \(b\)의 역원이 존재한다면 \((a/b) \pmod m\)을 다음과 같이 구할 수 있다.

\((a/b) \pmod m \equiv ((a \pmod m) \times (b^{-1} \pmod m)) \pmod m\)

곱셈 역원 구하기

단순한 방법

\(Z_m\)에서 어떤 수 \(b\)의 역원을 구하는 가장 단순한 방법은 1부터 \(m-1\)까지의 수를 모두 조사해보는 것이다. (시간복잡도: \(O(m)\))

int mulInverse(int b, int m) { for (int i = 1; i < m; i++) { if ((b * i) % m == 1) { return i; } } return -1; // not exist }

페르마의 소정리

만약 \(m\)이 소수인 경우에는 페르마의 소정리(Fermat's Little Theorem)을 이용하여 역원을 빠르게 구할 수 있다. \(m\)이 소수이고, \(a\)와 \(m\)이 서로소일 때, \(a^{m-1} \equiv 1 \pmod m\)이 성립한다. 따라서 \(a\)의 역원은 \(a^{m-2}\)가 된다.

확장 유클리드 알고리즘

만약 \(m\)이 소수가 아닌 경우에 \(b\)의 역원을 빠르게 찾고 싶다면 확장 유클리드 알고리즘(Extended Euclidean algorithm)을 이용하여 다음과 같은 식을 만족하는 \(x\)를 빠르게 찾으면 된다.

\(x \cdot b + y \cdot m \equiv 1 \pmod m\)

확장 유클리드 알고리즘은 두 정수 \(a\)와 \(b\)가 주어졌을 때, 다음식을 만족하는 두 정수 \(x, y\) 그리고 gcd(\(a\), \(b\)) 까지 동시에 계산한다. 보통 모듈로 안에서 곱셈에 대한 역원을 구할 때나, 중국인의 나머지 정리에서 해를 구할 때 사용될 수 있다.

int extGcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int g = extGcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g; }

중국인의 나머지 정리

중국의 오래된 수학책 '손자산경(孫子算經)'에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

이러한 형태의 문제는 중국인의 나머지 정리(Chinese Remainder Theorem)와 확장 유클리드 알고리즘을 이용하여 해결할 수 있다. 먼저 중국인의 나머지 정리는 다음과 같다.

각각 서로소인 자연수 \(m_1, m_2, ..., m_n\)과 임의의 정수 \(a_1, a_2, ..., a_n\)에 대하여, 다음 연립합동식은 법 \(m_1, m_2, ..., m_n\)에 대하여 유일한 해를 갖는다.

위 정리의 증명이자 연립합동식의 해 \(x\)를 구하는 과정은 다음과 같다.

1. \(M=m_1m_2...m_n\)이라 하고, \(u_k=M/m_k\)라 놓는다.
   
2. \(m_1, m_2, ..., m_n\)들은 각각 서로소이기 때문에 \(u_k\)와 \(m_k\) 역시 서로소, 즉 \(gcd(u_k, m_k)=1\) 이다.
3. 2에 의해 \(s_ku_k+t_km_k=1\)을 만족하는 정수 \(s_k, t_k\)가 존재한다. 이를 합동식 형태로 고치면 \(s_ku_k \equiv 1 \pmod {m_k}\)가 되고, 양변에 임의의 정수 \(a_k\)를 곱하면 \(a_ks_ku_k \equiv a_k \pmod {m_k}\)가 성립한다.
4. 이제 \(x=a_1u_1s_1+a_xu_2s_2+...+a_nu_ns_n \equiv a_k \cdot 1 \equiv a_k \pmod {m_k}\)가 성립하게 된다. 따라서 \(x\)가 주어진 연립합동식의 해가 된다.

위 과정에서 손으로 계산하기 까다로운 것이 \(s_ku_k+t_km_k=1\)을 만족하는 \(s_k\)인데 이는 앞서 설명한 확장 유클리드 알고리즘을 이용하여 구하면 된다.

예제

• BOJ 11401 이항 계수 3
• CF 785D Anton and School - 2

참고 자료

• JMBOOK, 구종만
  
• https://www.acmicpc.net/blog/view/29
• http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/