나머지


## 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  % C $$

$$ 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}$이므로, 쉽게 유도가 가능합니다.
