# 모듈러 산술 (Modular Arithmetic) ## 정의 **정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법**으로 쉽게 말해 **나머지를 이용한 산술 연산**이다.\ 사칙 연산과 마찬가지로 정수의 나머지에도 연산과 관련된 개념이 존재한다. ## 모듈러 산술 연산과 합동 ### 모듈러 산술 연산 나머지 연산을 하는 것으로 보통 언어에서 사용하는 `%` 연산과 비교하여 작성해보면 다음과 같다. * r = a % m (r : 나머지, a : 피제수, m : 제수) * r = a mod m ### 합동 (Congruent) 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인 것들을 모은다고 해보자. * 2 % 5 = 2 * 7 % 5 = 2 * 12 % 5 = 2 * ... 여기서 규칙성을 발견할 수 있는데 **나누는 수에 의하여 나누어지는 수 중 나머지가 같은 수는 나누는 수만큼의 차이가 존재한다. 즉, 5에 대한 나머지가 같은 수들의 집합에서 임의의 두 수를 꺼내도 항상 그 뺀 차이는 5로 나누어 떨어진다는 것**을 알 수 있다. ## 참조 {% embed url="" %} 모듈러 분배 법칙 {% endembed %} {% embed url="" %} 모듈러 산술 {% endembed %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://devlee.gitbook.io/docs/category/algorithm/modular-arithmetic.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.