> For the complete documentation index, see [llms.txt](https://devlee.gitbook.io/docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://devlee.gitbook.io/docs/category/algorithm/modular-arithmetic.md).

# 모듈러 산술 (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="<https://alive-wong.tistory.com/59>" %}
모듈러 분배 법칙
{% endembed %}

{% embed url="<https://sskl660.tistory.com/75>" %}
모듈러 산술
{% endembed %}