모듈로 연산(modulo operation)

Goal

• 모듈로 연산에 대한 이해
• 모듈로 덧셈, 뺄셈, 곱셈 연산에 대한 이해

---

모듈로 연산(Modulo Operation)이란?

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.

정수론에서 모듈라 연산(modular arithmetic)이란,
정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

*나눗셈 정리(division theorem)

두 정수로부터 몫과 나머지를 얻는 연산

나머지 있는 나눗셈(division with remainders) 또는 유클리드 나눗셈(Euclidean division)이라고도 한다.

*정의

정수 a와 양의 정수 b에 대하여

• $a = bq + r$을 만족하는 q, r이 유일하게 존재한다. (q는 몫, r은 나머지)
• $0 \leq r < b$ , 즉, r은 0보다 같거나 큰 정수(0또는 양의 정수)이다.

a : 제수(devidend)

b : 피제수(divisor)

q : 몫(quotient) => a div b == (a/b)

r : 나머지(remainder) => a mod b == (a%b)

*modular arithmetic 용어 정리

모듈로(modulo)

modulo operation에서 연산자를 의미 (mod 라고 표현, C++ 에서 %연산자가 이 역할을 한다.)

모듈로 연산(modulo operation)

나머지를 구하는 연산으로 A mod B 와 같은 형태로 표현한다.

modulus

나누는 수(제수)로 A mod B 에서, B가 modulus에 해당한다.

참고) modulo operation vs modular arithmetic

modulo operation : 단순히 연산만을 의미한다.

modular arithmetic : 더 포괄적인 개념으로, modulo operation을 사용한 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 연산과 합동 관계 등을 포함한 개념이다.

굳이 둘의 차이를 두지 않고 같은 의미로 사용되기도 한다.

---

모듈로 합동(congruent modulo)

두 정수 A, B와 양의 정수 C에 대해, 다음이 성립하면 모듈로 합동이라고 한다.

• A = B + K * C (K는 정수)

다음 식은 모듈로 합동의 동치이다. (기호 ≡ 로 표시)

• A ≡ B (mod C)
• A mod C = B mod C
• A = B + K * C (K는 정수) <=> A - B = K * C

*모듈로 합동이 아닌 경우 A $\not\equiv $ B (mod C) 로 표시

동치 관계(equivalence relation)

동치 관계 : '논리적으로 같은' 이항관계
쉽게 말하면 '그게 그거' 라는 말이다. ('같다' 는 개념의 일반화)

예를 들어 다음은 동치 관계이다.
$\cfrac{2}{3}$ 와 $\cfrac{4}{6}$ 는 서로 동치이다. 약분을 했냐 안했느냐의 차이지 사실상 같은 수이기 때문이다.

마찬가지로, modulo 연산에서도 다음 두 수 A, B는 mod C에 대해서 동치 관계이다.
A mod C = B mod C 이면, A, B는 동치 관계에 있다.

동치 관계의 표기 : A ~ B
`~` 표기는 A, B가 특정 동치 관계에 의해 동치 원소가 됨을 나타냄

동치 관계의 성립 조건
$x,y,z \in X$ 에 대하여 다음 조건이 성립하면 동치 관계에 있다고 한다.

• 반사관계(reflexive) : $x \sim x$
• 대칭관계(symmetric) : $ x \sim y $ 이면 $ y \sim x $ 이다.
• 추이관계(transitive) : $ x \sim y $ 이고 $ y \sim z $ 라면, $ x \sim z $ 이다.

동치 관계의 주요 성질

• 어떤 집합을 서로 공통 부분이 없으면서도(disjoint)
• 공집합이 아닌 클래스(equivalence class)들로
• 완벽하게 분할(partition) 가능

반사적,대칭적,추이적인 세 조건을 만족한다면, (즉, 동치 관계)
이 연산으로 이루어진 각 분할들은 동치류를 이루게 됨

*집합에서의 분할(partition) : 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다.
이 부분 집합은 다음을 만족한다.

• 공집합이 아니다.
• 각 부분 집합은 서로소 집합이다. (disjoint set)
• 모든 부분 집합을 모으면 전체 집합이 된다.

동치류(equivalence class) : 동치 관계에 있는 값들의 집합
즉, 그게 그거인 애들끼리 모아놓은 것이다.
표기 : [x]

예를 들어, mod 5에서 나머지가 1인 원소들의 집합 A에서 각 원소들은 동치류이다. (같은 집합에 속해있다)
A = {... , -4, 1, 6, ...}

다음 그림을 통해 모듈로 합동과 동치 관계에 대해 알아보자.

위 그림은 (mod C) 에 대한 연산을 나타낸다.
이때, 조각(동치류)의 개수는 C개(0 ~ C-1)이다.

• [0] : {..., -2C, -C, 0, C, 2C, ...}
• [1] : {..., -2C+1, -C+1, 1, C+1, 2C+1, ...}
• ...
• [C-1] : {..., -3C-1, -2C-1, C-1, -1, C-1, ...}

즉, (mod M)은 0 ~ C-1 숫자에 C의 배수를 더한 값의 집합이다.

위 그림에서 mod C에 대한 모듈로 합동은 다음 조건을 만족 시킨다.

• 반사성 : A ≡ A (mod C)
• 대칭성 : A ≡ B (mod C) 이면, B ≡ A (mod C)
• 추이성 : A ≡ B (mod C) 이고, B ≡ C (mod C) 이면, A ≡ C (mod C) 이다.

따라서, 모듈로 합동(congruent modulo)은 동치 관계(equivalence relation)이다.
이는 분할(partition)이 가능하고 분할된 원소들이 동치류(equivalence class)를 이룸을 의미한다.

---

모듈로 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)

덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현)

• 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M
• 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M
• 곱셈 : (a*b) % M = ((a*M) * (b*M)) % M

나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다.
모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재한다.

곱셈 역원은 다음과 같은 방법으로 구할 수 있다.

• 페르마의 소정리 (Fermat’s Little Theorem)
• 확장 유클리드 호제법 (Extended Euclidean Algorithm)

<참고>
모듈로 덧셈 증명
모듈로 곱셈 증명
모듈로 곱셈 역원 구하는 방법
모듈로 역원 구하는 방법 증명

*항등원과 역원

항등원(identity element) e

f(a,b)의 항등원 e는 f(x,e) = x 를 보장하는 값이다.

역원(inverse element)

f(a, b) = f(b,a) = e 인 b가 유일하다면 b는 a의 역원

모듈로 연산에서의 역원은 A * A^-1로 표현하고 다음을 만족시킨다.

$A * A^{-1} ≡ 1 (mod C)$ <=> $(A * A^{-1}) mod C = 1$

참고) 위키참고 (모듈로 연산 성질에 대해 자세히 정리되어 있음)
모듈로 연산의 성질

---

모듈로 연산의 사용처

모듈로 합동임을 활용하여 큰 정수를 다루거나 적은 수의 연산을 하기 위한 용도로 사용된다.

References

동치관계
모듈러연산
집합의분할
모듈로 역원
모듈로 역원 구하는 방법
모듈로 역원 구하는 방법 증명