모듈러 분배 법칙의 이해 - 나머지 연산 분배 법칙

사칙 연산과 마찬가지로, 정수의 나머지에 대해서도 연산 개념이 존재한다.

 

코딩 테스트에서 명시적으로 나머지 연산의 결과를 요구할 때가 있다. 또는 풀이 과정에서 나머지 연산 중 수가 너무 크다면(int 형을 벗어나게 된다면), 모듈러 분배 법칙을 적용해야할 수 있다.

 

최근에 풀었던 문제 중, 명시적으로 다음과 같은 구문이 있었다. 

 

- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

이런 경우, 수가 일반적인 범위(integer)를 벗어난다는 것을 명시적으로 알려주었기 때문에 추가적인 처리를 해주어야한다.

 

본인은 python을 사용하여 문제를 해결하여 Big Integer에 대한 문제를 고민하지 않아도 되지만, 나머지 연산 자체가 부하가 큰 연산이기 때문에 성능 측면에서 모듈러 분배 법칙을 적용했다.

 

모듈러 분배 법칙은,

 

(12345678 + 10000000) mod 17 = ( 12345678 mod 17 + 10000000 mod 17) mod 17

 

을 만족한다.

 

직접 확인해보기

 

이를 이용하면, 자료형이 엄격한 다른 언어에서도 모듈러 연산을 사용할 때, 오버플로우를 방지하고, 연산 시간을 줄일 수 있다.

---

# 모듈러 분배 법칙 알아보기

모듈러 법칙은 "나머지 연산"이로도 불린다.

 

C, Python에서는 "%" 연산자를 통해 기본적으로 지원한다. a % b의 결과는 a를 b로 나누고 남은 나머지를 의미한다.

---

합동식 - congruence

모듈러 분배 법칙을 공부하면서, 합동식이라는 개념을 알게되었다. 이는 정수론에서 찾을 수 있는 개념인데 다음과 같다.

 

임의의 정수 a, b, m에 대해서 m | ( a-b ) 일 때, a는 법 m에 대해서 b와 합동이다.

 

이를 기호로 표현하면, a ≡ b(mod m)이다. m는 합동의 법(modular)이라고 한다.

 

이를 이해하기 쉽게 표현하면, "a와 b를 m으로 나눈 나머지가 같다" 이다. 즉, "a mod m = b mod m"

 

최대 공약수를 빠르게 찾는 알고리즘 중 하나인 유클리드 호제법은 합동식의 특징을 이용한다.

---

모듈러 분배 법칙 증명

합동식 개념을 이용해서 모듈러 분배 법칙을 증명해보자. 모듈러 연산을 %로 표현한다.

 

임의의 정수 a, b, m에 대해서, (a + b) % m = (a % m + b % m) % m 이 성립함을 증명한다.

 

좌변 - (a + b) % m

1. (a + b) % m은 a + b을 m으로 나눈 나머지이다.
2. a % m = a  - m * k1, b % m = b - m * k2로 표현할 수 있다.
3. a + b - m * (k1 + k2) = a + b - m * k3 이므로, (a + b) % m = a % m + b % m은 성립한다.
4. 합동식으로 표현하면, a + b ≡ (a + b) mod m이다. 즉, a % m + b % m = (a + b) % m이다.

 

우변 - (a % m + b % m) % m

위의 증명에 따라 a + b

1. 위의 증명에 따라, a + b ≡ (a + b) mod m 이므로, a % m + b % m = (a + b) % m 은 성립한다.
2. 따라서,(a % m + b % m) % m = ((a + b) % m)  % m 이고, (a + b) % m를 m으로 나눈 나머지는 (a + b)를 m으로 나눈 나머지와 동일하다.
3. 따라서, (a+ b) % m ≡ (a + b) mod m

 

따라서,  (a + b) % m = a % m + b % m, (a % m + b % m) % m = ((a + b) % m) % m = (a + b) % m 이므로, 

 

(a + b) % m = (a % m + b % m) % m은 성립한다.

---

# 뺄셈과 곱셈의 모듈러 분배 법칙

모듈러 분배 법칙은 덧셈에만 국한되지 않고 곱셈과 뺄셈에도 적용된다.

 

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + p) % m # 음수 방지

 

이에 대한 증명은 생략하도록 한다.

 

합동식에 대해 정리하면서, 정수론의 0.001% 정도를 맛본 것 같다.

 

모든 학문은 가치있다는 것과 나는 우매한 생명체 하나일 뿐이다라는 것을 다시한번 느꼈다.