티스토리 뷰
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\)
곱셈 역원 구하기
단순한 방법
\(Z_m\)에서 어떤 수 \(b\)의 역원을 구하는 가장 단순한 방법은 1부터 \(m-1\)까지의 수를 모두 조사해보는 것이다. (시간복잡도: \(O(m)\))
페르마의 소정리
만약 \(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\)) 까지 동시에 계산한다. 보통 모듈로 안에서 곱셈에 대한 역원을 구할 때나, 중국인의 나머지 정리에서 해를 구할 때 사용될 수 있다.
중국인의 나머지 정리
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\)를 구하는 과정은 다음과 같다.
- \(M=m_1m_2...m_n\)이라 하고, \(u_k=M/m_k\)라 놓는다.
- \(m_1, m_2, ..., m_n\)들은 각각 서로소이기 때문에 \(u_k\)와 \(m_k\) 역시 서로소, 즉 \(gcd(u_k, m_k)=1\) 이다.
- 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}\)가 성립한다.
- 이제 \(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\)가 주어진 연립합동식의 해가 된다.
예제
참고 자료
- JMBOOK, 구종만
- https://www.acmicpc.net/blog/view/29
- http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/
'알고리즘 이론' 카테고리의 다른 글
탐색 (Searching) (0) | 2017.03.06 |
---|---|
Counting Sort, Radix Sort (0) | 2017.02.23 |
Suffix Array, LCP Array (0) | 2017.02.22 |
트리의 지름 (Diameter of Tree) (0) | 2017.02.20 |
KMP Pattern Searching (0) | 2017.02.20 |
- Total
- Today
- Yesterday
- divide and conquer
- Dynamic Programming
- Strings
- Data structure
- math
- Binary search
- branch and bound
- greedy
- sort
- sliding window
- pattern matching
- Fenwick Tree
- karatsuba
- Square root decomposition
- Minimum Spanning Tree
- implementation
- Segment Tree
- Graph
- tree
- Heap
- constructive algorithms
- kmp search
- BFS
- search
- parametric search
- suffix array
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |