모듈러 산술(Modular Arithmetic)

*모듈러 산술(Modular Arithmetic)

-> 모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법을 말한다.

-> 쉽게 말해 나머지를 이용한 산술 연산이라고 생각하면 된다. 사칙 연산과 마찬가지로 정수의 나머지에도 연산과 관련된 개념이 존재한다. 

-> 모듈러 연산은 정수론, 컴퓨터 과학의 보안 등 여러 분야에서 유용하게 사용될 수 있다. 알고 있다면 알고리즘 문제에서 몇몇 연산을 편하게 할 수 있는 방법을 생각하는 기반이 될 수 있다. 모듈러 연산 자체를 응용한 문제는 그렇게 많지 않지만, 이를 기반으로한 수학적 개념(정수론)의 기반이 되기 때문에 이해해두도록 하자.

 

*모듈러 산술 연산과 합동(Congruent)

-> 모듈러 산술 연산 : 쉽게 말해 나머지 연산을 하는 것을 말한다. 보통 언어에서 사용하는 %연산과 비교하여 작성해보면 다음과 같다.

mod 연산의 정의

-> 합동(Congruent) : mod 연산은 합동 관계를 바탕으로 두 수의 관계를 정의하는 경우가 많이 있다.

합동 관계의 정의

※ m | (a - b)에서 | 의 의미는 (a - b)는 m으로 나누어 떨어진다는 의미이다. 쉽게 말해, 10은 2로 나누어 떨어진다는 것을 수학적으로 표현하면 2 | 10이다. 나누어 떨어지지 않는 경우는 ł 라는 기호를 이용하여 표현한다.

※ 쉽게 말해 a - b가 m이라는 정수로 나누어 떨어진다면, a ≡ b (mod m)과 같이 표현하겠다라는 의미라고 생각하면 된다.

※ 이는 다르게 말하면, a와 b는 m에 의하여 나눠 졌을때의 나머지가 동일하다는 것을 의미한다. 이것을 조금 더 직관적으로 이해하기 위하여 예를 들어보면 어떤 수를 5로 나눌 때, 그 수의 나머지가 2인 것들을 모아서 생각해 보도록 하자. 그럼 아래와 같이 나열할 수 있을 것이다.

이때, 나누어지는 수들의 관계를 분석해보면 나누는 수 5에 의하여 나누어지는 수들 중 나머지가 같은 수(2, 7, 12...)는 나누는 수 만큼의 차이가 존재한다는 것을 알 수 있다. 즉, 5에 대한 나머지가 같은 수들의 집합에서 임의의 두 수를 꺼내서 빼도 항상 그 뺀 차이는 5로 나누어 떨어진다는 것을 알 수 있다. 따라서 이러한 규칙성을 m | (a - b)라고 표현한 것 뿐이고, 그것을 수식으로 표현한 것이다 a ≡ b (mod m)일 뿐이다.

 

*모듈러 산술 연산의 특징

-> 모듈러 산술 연산은 분배 법칙이 성립한다.

덧셈, 뺄셈, 곱셈에 대한 모듈러 산술 연산 분배 법칙

 나눗셈의 경우 곱셈의 역원을 이용하여 분배법칙을 적용시킬 수 있다.

-> 예를 들면 (5 + 11) mod 7 = (5 mod 7 + 11 mod 7) + mod 7 = 2임을 알 수 있다.

 

*합동식의 성질

-> 사실상 이 글의 핵심으로, 모듈러 산술을 적용하기 위한 기본 재료가 되는 개념들이다. 증명에 대해서 이해를 해두는 것도 좋지만, 이 글은 알고리즘 문제에서 주로 사용되는 합동식의 성질 이해를 위주로 작성하겠다. 합동식의 성질에 대한 증명은 나무위키의 합동식 문서의 '성질' 문단에서 참고할 수 있다.

namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D

합동식 - 나무위키

(1) 덧셈, 뺄셈, 곱셈에 관련된 성질

덧셈, 뺄셈에 관련된 성질

-> 쉽게 말해 a와 b로 m으로 나눈 나머지가 같고 c와 d를 m으로 나눈 나머지가 같으면 a ± c 와 b ± d 를 m으로 나눈 나머지도 같다는 의미이다. 예를 들면 49 ≡ 1 (mod 8)이고 37 ≡ 5 (mod 8)일 때 위의 성질에 의하여 86 ≡ 6 (mod 8)임을 알 수 있다.

곱셈에 관련된 성질

-> 위의 성질과 별로 다른 점이 없다. 곱셈에 대해서도 똑같은 논리가 적용된다. 예를 들면 33 ≡ 5 (mod 7)이고 122 ≡ 17 (mod 7)일 때 위의 성질에 의하여 4026 ≡ 85 (mod 7)임을 알 수 있다.

 

(2) 거듭 제곱에 관련된 성질

거듭 제곱에 관련된 성질

-> 이 역시 쉽게 말하면, a와 b를 m으로 나눈 나머지가 동일 하다면, 각 숫자를 동일하게 거듭제곱한 숫자를 m으로 나눈 나머지도 동일하다는 의미를 갖는다. 예를 들면 77 ≡ 7 (mod 8)일 때, 77^10 ≡ 7^10 (mod 8)도 성립한다는 것을 알 수 있다. 

 

*합동식의 성질의 활용

-> 합동식의 성질을 활용하면 다음과 같이 일반적으로는 계산하기 힘든 문제도 간단하게 해결할 수 있다.

※ 3^333의 1의 자리수를 구하시오.

-> 1의 자리수를 구한다는 것은, 해당 숫자를 10으로 나눈 나머지를 구한다는 것과 같은 의미이다(특정 자리수를 구하는 것은 대상 숫자를 10의 거듭제곱 중 하나로 나누어 구할 수 있다). 

-> 우선 거듭 제곱에 관련된 모듈러 산술의 성질을 이용하여 접근하기 위해 작은 숫자부터 규칙성을 찾아보자. 3 ^ 4 ≡ 1 (mod 10)이고, 따라서 거듭 제곱의 성질을 적용하면 3 ^ 332 ≡ 1 ^ 83 (mod 10)임을 알 수 있다. 즉 이 식은 3 ^ 332 ≡ 1 (mod 10)과 같고, 곱셈에 관련된 모듈러 산술의 성질을 이용하면 3 ^ 333 = 3 (mod 10)임을 알 수 있다. 따라서 3 ^333의 1의 자리수는 3임을 알 수 있다.

-> 물론 1의 자리수가 반복되는 규칙성을 이용해서도 문제를 해결할 수 있지만, 해당 문제를 풀기 위해 사용한 모듈러 산술의 아이디어를 활용하면 1, 10, 100의 자리 등을 구할 수 있음을 알 수 있다.