1. 모듈러 연산의 기초
예전에 모듈러 연산과 관련된 포스팅을 올린 적이 있습니다.
모듈러 연산의 분배 법칙을 알아보았지만, 나눗셈의 분배 법칙은 키워드 정도만 안내하고 넘어갔습니다.
\((a+b) \text{ mod } c = \big((a \text{ mod }{c}) + (b \text{ mod }{c})\big) \text{ mod }{c} \)
\((a-b) \text{ mod }{ c } = \big((a \text{ mod }{c}) - (b \text{ mod }{c})\big) \text{ mod }{c} \)
\((a \times b) \text{ mod }{ c } = \big((a \text{ mod }{c}) \times (b \text{ mod }{c})\big) \text{ mod }{c} \)
\(\mathbf{(a \div b) \text{ mod }{ c } \neq \big((a \text{ mod }{c}) \div (b \text{ mod }{c})\big) \text{ mod }{c}} \)
https://kimwooil.tistory.com/57
[57] 모듈러? 모듈로? 나머지와 관련된 이야기
1. 계산 결과를 1,000,000,007로 나눈 나머지를 출력하세요. 알고리즘 문제를 풀다보면 가끔 이런 문장을 만나곤 합니다. 주로 큰 수를 결과로 출력하기 위한 문제들에서 보입니다. 그 이유는 컴퓨터
kimwooil.tistory.com
이번 포스팅에서 나눗셈에서 모듈러 연산의 분배 법칙을 알아봅시다.
2. 곱셈의 역원
어떤 수와 연산을 했을 때 결과가 다시 그 수가 나오게 하는 수를 해당 연산의 항등원이라고 합니다.
\((a\pm\Box)\text{ mod }{b} = \big((a \text{ mod }{b}) \pm (\Box \text{ mod }{b})\big) \text{ mod }{b} = a \text{ mod }{b}\)
모듈러 덧셈, 뺄셈 연산의 항등원은 0입니다.
어떤 수와 연산을 했을 때 결과가 항등원이 나오게 하는 수를 해당 연산의 역원이라고 합니다.
\((a\pm\Box)\text{ mod }{b} = \big((a \text{ mod }{b}) \pm (\Box \text{ mod }{b})\big) \text{ mod }{b} = 0\)
어떤 정수 a의 덧셈, 뺄셈의 역원은 \(\mp a \text{ mod }{b}\)입니다.
\((a\times\Box)\text{ mod }{b} = \big((a \text{ mod }{b}) \times (\Box \text{ mod }{b})\big) \mod {b} = a \text{ mod }{b}\)
모듈러 곱셈의 항등원은 1입니다.
\((a\times\Box)\text{ mod }{b} = \big((a \text{ mod }{b}) \times (\Box \text{ mod }{b})\big) \mod {b}= 1\)
곱셈의 역원은 연산 결과가 1이 나와야 합니다.
모듈러 연산의 값이 1이라면 피연산자는 서로소여야 합니다.
왜냐하면, 아니라고 했을 때 서로소가 아닌 a, b에서 \(a \text{ mod }{b} = 1 \)이 가능해야하는데,
그렇다면 ax + by = 1 을 만족하는 정수 x, y가 존재해야하지만, a와 b가 서로소가 아니므로 공통 약수 d로 나누어 지므로,
\(d \times (\dfrac{a}{d}x + \dfrac{b}{d}y) = 1\) 여기서 좌변은 d의 배수이므로 d는 1, 즉 a와 b는 서로소여야만 합니다.
다시 말해, 곱셈의 역원이 존재하려면 a와 b는 서로소여야 합니다.
이제 ax + by = 1을 만족하는 정수해 x, y를 구하면 x가 a의 곱셈 역원이 되는 것을 알 수 있습니다.
3. 하나씩 넣어보기
\(278 (\text{mod }29)\)의 곱셈의 역원을 구해봅시다.
\((278\times\Box)\text{ mod }{27} = 1\)
위 식을 만족하는 ㅁ를 찾기 위해 하나씩 넣어봅니다.
\(\begin{align}(278\times1)\text{ mod }{29} &= 278 \text{ mod }{29} = 17 \\ (278\times2)\text{ mod }{29} &= 556 \text{ mod }{29} = 5 \\ (278\times3)\text{ mod }{29} &= 834 \text{ mod }{29} = 22 \\ (278\times4)\text{ mod }{29} &= 1112 \text{ mod }{29} = 10 \\& ... \\ (278\times12)\text{ mod }{29} &= 4726 \text{ mod }{29} = 1 \end{align}\)
1 부터 하나씩 넣어보니 12번째에 1이 나옵니다.
278의 곱셈 역원은 12입니다.
맞는지 확인해봅시다.
278에 123을 곱한 수는 34194입니다.
다시 말해 \(34194 \div 278 = 123\) 입니다.
278로 나누는 대신 역원인 12를 곱해서 다음과 같이,
\((34194\text{ mod }29) \times (12\text{ mod }29) = 123\text{ mod }29 \equiv 7(\text{mod }29)\) 가 되는지 확인해보면,
\(3 \times 12 = 36 \equiv 7(\text{mod }29)\) 으로 나눗셈도 곱셈의 역원을 이용해 분배법칙을 사용할 수 있습니다.
4. 확장 유클리드 알고리즘
호제법으로 278과 29의 공약수를 구해봅시다. 서로소이므로 결과는 당연히 1이지만 과정을 살펴봅시다.
278
29
17
12
5
2
1
조금 더 자세히 과정을 써보면 다음과 같습니다.
\(278 \times \mathbf{12} + 29 \times (-115) = 1\)
확장 유클리드 알고리즘을 통해 ax + by = 1 꼴로 나타내었고,
\(278 (\text{mod }29)\)의 곱셈의 역원이 12라는 것을 알 수 있습니다.
5. 페르마의 소정리
페르마의 소정리는 다음과 같습니다.
p가 소수이면, 모든 정수 a에 대해 \(a^{p} \equiv a(\text{mod }p)\) 이다.
만약 a와 p가 서로소이면, \(a^{p-1} \equiv 1(\text{mod }p)\) 이다.
따라서
\(a^{p-1} = a \times a^{p-2} \equiv 1(\text{mod }p)\)
위 식이 성립하고, a의 곱셈 역원은 \(a^{p-2}\)가 됩니다.
278과 29의 경우
\(278 \times 278^{29-2} \equiv 1(\text{mod }p)\)
이고, \(278^{29-2} \text{ mod }29\)는 12가 됩니다.
거듭제곱이 큰 수일 경우, 분할 정복을 통해 빠르게 계산할 수 있습니다.
