modulo

Intro

해당 Posting에서는 Modulo연산의 정의와 특징을 이해하고, 이를 이용한 알고리즘을 소개합니다.

사칙연산과 같은 연산자입니다. 하지만, modulo 연산은 기존 사칙연산과는 다른 다양한 특징을 가지기 때문에, 이를 정리하고 이해하는 것은 중요합니다.

Modulo 연산

우선 modulo 연산이란 무엇인지부터 알아야 합니다.

$a = bq + r$

$r = a \mod b = a \mod q$

ex.

1. $100 \mod 3 = 1$
2. $12 \mod 32 = 12$
3. $123 \mod 11 = 2$
4. $1 \mod 1 = 0$

로 정의할 수 있습니다.

쉽게 말해서, a와 b에 대해서, 나눗셈한 나머지를 반환하는 연산자입니다.

이는 여러 programming language에서는 % 표기로 나타내는 경우가 많습니다. 따라서, 아래에서 부터는 %로 표기합니다.

이 연산자는 기타 여러 알고리즘에서 유용하게 사용되기 때문에 특징을 알아두는 것이 좋습니다.

특징

1. 연산 결과는 0보다 크거나 같고 연산을 수행하는 값($b$)보다는 작습니다.
2. 만약, modulo 연산을 했을 때, 결과가 같다면, 두 정수는 합동이라고 합니다. 이에 따라, 합동인 정수는 무한히 많습니다.

연산 특징

1. 덧셈의 항등원(0)이 존재합니다.
   $(A + 0) \% C = A \% C$
2. 덧셈의 역원(-A = C-A)이 존재합니다.
   $-A \% C = (C - A) \% C$
   ex) $-105 \% 100 = -5 \% 100 = 95$
3. $(A+B) \% C = \{(A\%C) + (B\%C)\} \% C$
   ex) $54 \% 17 = \{(29\%17) + (25\%17)\} \% 17 = (12+8) \%17 = 3$
4. $(A-B) \% C = \{(A\%C) - (B\%C)\} \% C$
   ex) $54 \% 17 = \{(70\%17) - (16\%17)\} \% 17 = (2-16) \%17 = -14 \% 17 = 3$
5. $(A \times B) \% C = \{(A\%C) \times (B\%C)\} \% C$
   ex) $960 \% 17 = \{(20\%17) \times (18\%17)\} \% 17 = (3 \times 1) \%17 = 3$
6. 정수 k, p에 대하여, p가 k의 약수라면,
   $A^k \% C = (A^{k \over p}\%C)^p \% C$
   ex) $2^{10}(=1024) \% 29 = (2^5(=32) \% 29)^2 \%29 = 3^2 \% 29 = 9$
7. 곱셈의 항등원(1)이 존재합니다. ($C \ge 2$)
   $A \times 1 \% C = A \% C$
8. 곱셈의 역원(A^{-1})가 존재합니다.
   $A \times A^{-1} \% C = 1$
   하지만, 이를 구하는 것은 직접 해보는 수밖에 없습니다.
9. 곱셈의 역원을 통해서 나눗셈을 정의할 수 있습니다.
   $({B \over{A}} ) \% C = B \times A^{-1} \% C$

위와 같은 특징들 때문에, 수의 범위를 제한하는 문제를 푼다고할 때, 굉장히 유용하게 이를 이용할 수 있습니다. 왜냐하면, modulo 합동끼리는 사칙연산의 여러 특징들을 모두 사용할 수 있기 때문입니다.

교환 법칙, 결합법칙, 역원, 항등원이 모두 존재합니다.

또한, 만약, 나누는 수가 만약 소수라면, 나눗셈을 더 쉽게 정의할 수 있습니다.

바로 Fermat's little theorem(페르마의 소정리)를 활용하는 것입니다.

이에 따르면, $A^{n-1} \% C = 1$이라는 것입니다.

이를 통해서, 우리는 아래를 증명할 수 있으며,

$A \times A^{-1} \% C = 1$

$A \times A^{-1} \% C = A^{n-1} \% C$

$A^{-1} \% C = A^{n-2} \% C$

결론상 다음과 같이 나눗셈을 변형할 수 있습니다.

${A\over B} \% C = A\times B^{n-2} \% C$

유클리드 호제법

최대공약수(GCD), 최소공배수(LCM)를 구하는 문제에서 가장 단골로 사용되는 알고리즘입니다.

해당 알고리즘의 동작순서는 다음과 같습니다.

1. 큰 수(p)로 작은 수(q)를 modulo 연산하여, 결과값(r)을 얻습니다.
2. r이 0이라면, q는 최대공약수입니다.
3. 그렇지 않다면, q와 r을 갖고, 1로 돌아가서 다시 시행합니다.

이 결과를 통해서, 최대공약수(GCD)를 구할 수 있고, 모두가 알다시피, 최소공배수는 ${p \times q}\over {gcd}$이므로, 쉽게 유도가 가능합니다.