모듈러 산술 (Modular Arithmetic)

모듈러 산술에 대해 서술합니다.

정의

정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법으로 쉽게 말해 나머지를 이용한 산술 연산이다. 사칙 연산과 마찬가지로 정수의 나머지에도 연산과 관련된 개념이 존재한다.

나머지 연산을 하는 것으로 보통 언어에서 사용하는 % 연산과 비교하여 작성해보면 다음과 같다.

mod 연산은 합동 관계를 바탕으로 두 수의 관계를 정의하는 경우가 많다.

고정된 양의 정수 m(!= 1) 에 대해 두 정수 a, b가 m | (a - b) 를 만족할 때, a 와 b 는 m 을 법으로한 합동 또는 합동식이라고 부르고 기호로는 a = b (mod m) 으로 표현한다.

여기서 | 의 의미는 (a - b) 는 m 으로 나누어 떨어진다는 의미로 a - b 가 m 으로 나누어 떨어진다면 a = b (mod m) 으로 표현하겠다는 것이다. 다르게 말하면 a 와 b 는 m 에 의하여 나눠 졌을 때의 나머지가 동일하다는 것을 의미한다.

예를 들어 어떤 수를 5로 나눌 때 그 수의 나머지가 2인 것들을 모은다고 해보자.

여기서 규칙성을 발견할 수 있는데 나누는 수에 의하여 나누어지는 수 중 나머지가 같은 수는 나누는 수만큼의 차이가 존재한다. 즉, 5에 대한 나머지가 같은 수들의 집합에서 임의의 두 수를 꺼내도 항상 그 뺀 차이는 5로 나누어 떨어진다는 것을 알 수 있다.

Last updated 3 months ago