모듈러 산술

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

모듈러 산술은 정수를 특정 정수(법)로 나눈 나머지를 이용한 산술 체계이다. 두 정수가 법에 대해 합동이라는 것은 그 차이가 법의 배수인 경우를 의미하며, 이는 동치 관계를 형성한다. 모듈러 산술은 덧셈, 뺄셈, 곱셈 연산과 호환되며, 컴퓨터 과학, 암호학, 수론 등 다양한 분야에 응용된다. 특히, RSA, 디피-헬만과 같은 공개 키 암호화 시스템과 ISBN, IBAN과 같은 일련 번호의 오류 검출에 활용된다. 가우스는 합동 산술을 체계화하여 정수론 발전에 기여했으며, 19세기 이후 추상대수학 등 다양한 분야로 확장되었다.

모듈러 산술

📚 더 읽어볼만한 페이지

유한환 - 자명환
자명환은 원소 0 하나로 이루어진 집합에 덧셈과 곱셈을 정의하여 환 구조를 부여한 것으로, 덧셈과 곱셈에 대한 항등원이 일치하는 유일한 환이며 환의 범주에서 종대상 역할을 한다.
가환대수학 - 매개계
매개계는 뇌터 국소 가환환과 유한 생성 가군을 사용하여 정의되며, 가군의 길이와 크룰 차원을 활용하여 정칙 국소환에서 정칙 매개계의 성질을 규명하고, 추상대수기하학에서 기하학적 대상의 분류와 연구에 중요한 역할을 한다.
가환대수학 - 크룰 차원
크룰 차원은 환 내의 소수 아이디얼 체인의 길이를 이용하여 정의되며, 환론 및 대수기하학에서 중요한 역할을 하고 다양한 개념으로 확장되어 사용된다.
수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

2. 정의

$n\in\mathbb Z$ 이 2 이상의 정수라고 하자. 정수환 $\mathbb Z$ 의 주 아이디얼 $(n)$ 에 대한 몫환 $\mathbb Z/(n)$ 의 원소들은 $\{0,1,\dots,n-1\}$ 과 일대일 대응하며, 이는 정수를 $n$ 으로 나눈 나머지로 생각할 수 있다. 즉, 환 준동형
: $\phi_n\colon\mathbb Z\to\mathbb Z/(n)$
을, 정수를 $n$ 에 대한 나머지로 대응시키는 함수로 여길 수 있다.

임의의 두 정수 $a,b\in\mathbb Z$ 에 대하여 다음 두 조건이 서로 동치이며, 이 조건이 성립하면 $a$ 와 $b$ 가 법 $n$ 에 대하여 합동(congruent modulo $n$ ^영어)이라고 한다.
* $a=b+kn$ 인 정수 $k\in\mathbb Z$ 가 존재한다.
* $\phi_n(a)=\phi_n(b)\in\mathbb Z/(n)$ 이다. 즉, $a$ 와 $b$ 는 $\mathbb Z/(n)$ 의 같은 동치류에 속한다.
이는 기호로는
: $a\equiv b\pmod n$
이라고 한다. 정수의 합동은 동치 관계를 이룬다.

예를 들어 12를 법으로 할 때,
: $38 \equiv 14 \pmod {12}$
가 성립하는데, 그 이유는 38과 14를 12로 나눈 나머지가 2로 같기 때문이다. 이는 38 - 14 = 24 = 2 × 12 와 같이 12의 배수로 표현되는 것과 동치이다.

합동의 정의는 음수 값에도 적용된다. 예를 들어,
: $\begin{align}2 &\equiv -3 \pmod 5\\-8 &\equiv 7 \pmod 5\\-3 &\equiv -8 \pmod 5.\end{align}$

2.1. 합동 관계

congruent modulo n^영어이라고 불리는 합동 관계는 덧셈, 뺄셈, 곱셈 연산과 호환되는 동치 관계이다.

정수 이 주어졌을 때, 이를 법이라고 부르며, 두 정수 와 는 이 두 수의 차이를 나누는 수, 즉 다음을 만족하는 정수 가 존재하면 을 법으로 하는 합동이라고 한다.
: .

을 법으로 하는 합동은 다음과 같이 표기한다.
: .

괄호는 이 오른쪽 항()뿐만 아니라 전체 방정식에 적용된다는 것을 의미한다.

합동 관계는 다음과 같이 다시 쓸 수 있다.
: ,
이는 유클리드 나눗셈과의 관계를 명시적으로 보여준다.

을 법으로 하는 합동은 으로의 나눗셈 가능성에 의해 정의되고, 은 정수 링의 단위이기 때문에, 어떤 수가 으로 나누어 떨어지는 것은 정확히 으로 나누어 떨어지는 것과 같다.
이는 모든 0이 아닌 정수 을 법으로 사용할 수 있음을 의미한다.

합동 관계는 다음의 모든 동치 관계 조건을 만족한다.
* 반사율:
* 대칭성: 이면 이다.
* 추이성: 만약 이고 이면, 이다.

만약 이고 이거나, 이면:
* (덧셈과의 호환성)
* (뺄셈과의 호환성)
* (곱셈과의 호환성)

3. 성질

합동 관계는 동치 관계의 모든 조건을 만족한다.

* 반사율:
* 대칭성: 이면 이다.
* 추이성: 이고 이면, 이다.

이고 이거나, 이면:
* 임의의 정수 에 대해 (평행이동과의 호환성)
* 임의의 정수 에 대해 (스케일링과의 호환성)
* 임의의 정수 에 대해
* (덧셈과의 호환성)
* (뺄셈과의 호환성)
* (곱셈과의 호환성)
* 임의의 음이 아닌 정수 에 대해 (지수 연산과의 호환성)
* 정수 계수를 갖는 임의의 다항식 에 대해 (다항식 평가와의 호환성)

이면, 일반적으로 은 거짓이다. 하지만 다음은 참이다.
* 이고, 가 과 서로소이면 이다. ( 는 오일러의 토션트 함수)

공통 항의 소거에는 다음과 같은 규칙이 있다.
* 이고, 가 임의의 정수이면, 이다.
* 이고 가 과 서로소이면, 이다.
* 이고 이면, 이다.

마지막 규칙은 모듈러 산술을 나눗셈으로 이동하는 데 사용될 수 있다. 가 를 나누면, 이다.

모듈러 곱셈 역원은 다음 규칙에 의해 정의된다.
* 존재성: 정수 가 존재하여 가 성립하는 것은 가 과 서로소일 때뿐이다. 이 정수 는 모듈로 의 의 모듈러 곱셈 역원이라고 불린다.
* 이고 가 존재하면, 이다 (곱셈 역원과의 호환성 및 일 때 모듈로 의 유일성).
* 이고 가 과 서로소이면, 이 선형 합동식의 해는 로 주어진다.

곱셈 역원 는 베주 방정식 을 , 에 대해 풀어서 확장된 유클리드 알고리즘을 사용하여 효율적으로 계산할 수 있다.

특히, 가 소수이면, 인 모든 에 대해 는 와 서로소이다. 따라서 0 모듈로 에 합동이 아닌 모든 에 대해 곱셈 역원이 존재한다.

합동 관계의 몇 가지 더 진보된 속성은 다음과 같다.

* 페르마의 소정리: 가 소수이고 를 나누지 않으면, 이다.
* 오일러의 정리: 와 이 서로소이면, 이다. 여기서 는 오일러의 피 함수이다.
* 페르마의 소정리의 간단한 결과로, 가 소수이면, 는 의 곱셈 역원이다. 더 일반적으로, 오일러의 정리에서 와 이 서로소이면, 이다. 따라서 이면, 이다.
* 또 다른 간단한 결과는 이면, 이다. 단, 가 과 서로소인 경우에 한한다. ( 는 오일러의 피 함수)
* 윌슨의 정리: 가 소수일 필요충분 조건은 이다.
* 중국인의 나머지 정리: 임의의 , 와 서로소인 , 에 대해, 이고 인 유일한 가 존재한다. 실제로, 이다. 여기서 은 의 법 에 대한 역원이고 은 의 법 에 대한 역원이다.
* 라그랑주의 정리: 가 소수이고 가 정수 계수를 갖는 다항식이며 가 의 약수가 아니면, 합동식 는 최대 개의 서로 합동하지 않은 해를 갖는다.
* 법 에 대한 원시 근: 숫자 는 과 서로소인 모든 정수 에 대해 가 되는 정수 가 존재하면 법 에 대한 원시 근이다. 법 에 대한 원시 근은 이 , , 또는 일 때 존재한다. 여기서 는 홀수 소수이고 는 양의 정수이다. 법 에 대한 원시 근이 존재하면, 정확히 개의 이러한 원시 근이 있다. ( 는 오일러의 피 함수)
* 2차 잉여: 정수 는 어떤 정수 에 대해 가 존재하면 법 에 대한 2차 잉여이다. 오일러의 기준에 따르면, 가 홀수 소수이고 가 의 배수가 아니면, 는 인 경우에만 법 에 대한 2차 잉여이다.

3.1. 기본 성질

합동 관계는 다음의 모든 동치 관계 조건을 만족한다.

* 반사율:
* 대칭성: 이면 이다.
* 추이성: 만약 이고 이면, 이다.

만약 이고 이거나, 이면:

* 임의의 정수 에 대해 (평행이동과의 호환성)
* 임의의 정수 에 대해 (스케일링과의 호환성)
* 임의의 정수 에 대해
* (덧셈과의 호환성)
* (뺄셈과의 호환성)
* (곱셈과의 호환성)
* 임의의 음이 아닌 정수 에 대해 (지수 연산과의 호환성)
* 임의의 다항식 에 대해 정수 계수가 있는 (다항식 평가와의 호환성)

3.2. 덧셈 · 뺄셈 · 곱셈

$\mathbb Z/(n)$ 은 가환환이므로, 덧셈, 뺄셈, 곱셈을 정의할 수 있다. 덧셈과 곱셈은 결합 법칙과 교환 법칙을 따르며, 분배 법칙도 성립한다.

정수 $m \ge 1$ 이 주어졌을 때, 이를 '법'이라고 부른다. 두 정수 $a$ 와 $b$ 에 대해, $m$ 이 두 수의 차이를 나누면, 즉 다음을 만족하는 정수 $k$ 가 존재하면, $a$ 와 $b$ 는 ' $m$ 을 법으로 하는 합동'이라고 한다.

: $a - b = k m$ .

$m$ 을 법으로 하는 합동은 합동 관계라고 하며, 이는 덧셈, 뺄셈, 곱셈 연산과 호환되는 동치 관계이다. $m$ 을 법으로 하는 합동은 다음과 같이 표기한다.

: $a \equiv b \pmod m$ .

이 합동 관계는 다음과 같이 다시 쓸 수 있다.

: $a = k m + b$

이는 유클리드 나눗셈과의 관계를 보여준다. 여기서 $b$ 는 $a$ 를 $m$ 으로 나눈 나머지가 아니어도 된다. 대신, $a \equiv b \pmod m$ 은 $a$ 와 $b$ 가 $m$ 으로 나눌 때 같은 나머지를 갖는다는 것을 의미한다. 즉,

: $a = p m + r$ ,
: $b = q m + r$

여기서 $0 \le r < m$ 은 공통 나머지이다.

3.3. 나눗셈

모듈러 산술에서 나눗셈은 일반적인 체와 달리 항상 정의되지는 않는다. 하지만, 특정한 조건 아래에서는 나눗셈과 유사한 연산을 정의할 수 있다.

* 법이 소수인 경우: 법 $n$이 소수이면, $\mathbb{Z}/(n)$은 체가 된다. 이 경우 0을 제외한 모든 원소는 곱셈에 대한 역원을 가지므로, 나눗셈이 가능하다.
* 법이 합성수이고 서로소인 경우: 법 $n$이 합성수일 때는, $n$과 서로소인 수만이 가역원이 되어 역수를 정의할 수 있다. 오일러의 정리에 따르면, $a$가 $n$과 서로소일 때, $a^{\phi(n)}\equiv 1 \pmod n$이 성립한다. 여기서 $\phi$는 오일러 피 함수이다. 즉, $n$개의 합동류 중 $\phi(n)$개만이 가역원이며, 가역원 $a$의 역원은 $a^{\phi(n)-1}$이다.

예를 들어, 법 4에 대한 최소 잉여계는 {0, 1, 2, 3}이다. 이 중 1과 3은 4와 서로소이므로 가역원이다. 1의 역원은 1이고, 3의 역원은 3이다. (3 * 3 = 9 ≡ 1 (mod 4)).

3.3.1. 홀수 소수의 거듭제곱

2가 아닌 소수 $p$ 에 대하여, $\mathbb Z/(p^k)$ 의 가역원들은 총 $\phi(p^k)=p^{k-1}(p-1)$ 개가 있으며 ( $\phi$ 는 오일러 피 함수), 그 가역원군은 순환군이다.
: $(\mathbb Z/(p^k))^\times\cong Z_{\phi(p^k)}$

3.3.2. 2의 거듭제곱

$k>1$ 에 대하여, $\mathbb Z/(2^k)$ 의 가역원군은 다음과 같다.

: $(\mathbb Z/(2^k))^\times\cong Z_2\times Z_{2^{k-2}}$

3.3.3. 일반적 합성수

일반적인 합성수의 경우, 가역원군은 중국인의 나머지 정리에 따라 다음과 같이 분해된다.

: $\left(\mathbb Z/\left(\prod_pp^{n_p}\right)\right)^\times\cong\prod_p(\mathbb Z/(p^{n_p}))^\times$

3.4. 중국인의 나머지 정리

중국인의 나머지 정리에 따르면, n의 소인수 분해가 다음과 같을 때,
: $n=\prod_pp^{n_p}$
다음과 같은 가환환의 동형이 존재한다.
: $\mathbb Z/(n)\cong\prod_p\mathbb Z/(p^{n_p})$
즉, 두 개 이상의 소인수를 갖는 수에 대한 모듈러 산술은 그 소인수들(의 거듭제곱)에 대한 합동류들을 성분별로 취급하는 것과 같다.

3.5. 오일러의 정리

modulo^영어 을 법으로 하는 각 잉여류는 그 구성원 중 하나로 표현될 수 있지만, 일반적으로 각 잉여류는 해당 잉여류에 속하는 가장 작은 음이 아닌 정수로 표현한다. 서로 다른 잉여류의 두 구성원은 을 법으로 할 때 서로 합동이 아니다. 게다가 모든 정수는 을 법으로 하는 단 하나의 잉여류에 속한다.

디리클레는 서로소인 정수 , 과 양의 정수를 넘나드는 변수 에 대해 의 형태로 쓸 수 있는 수에 주목했고, 이러한 수의 세계에서 소수가 실제로 무수히 존재함을 보이려 시도했다. 그러한 문제에 대해 합동 산술은 유효한 도구이며, 이는 즉 잉여류에서 소수 전체가 이루는 집합의 농도를 아는 것과 같다.

디리클레는 법 에 관해 가역원 전체가 이루는 군 (환 의 단위군, 즉 기약 합동류군 ))을 생각하고, 그 군에서 영이 아닌 복소수 전체가 이루는 곱셈군으로의 군 준동형 (즉, 군의 원소 , 에 대해 를 만족하는 사상) 전체가 이루는 집합에 대해 조사했다. 이러한 사상을 디리클레 지표라고 한다. 디리클레 지표는 개 존재하며, 두 지표의 곱은 또한 하나의 지표이며, 곱셈표를 쓰면 이는 기약 합동류군의 것과 완전히 똑같아진다.

3.6. 페르마의 소정리

페르마의 소정리는 오일러의 정리의 특수한 경우로, 법이 소수일 때 성립한다.

3.7. 윌슨의 정리

현대적인 용어로 말하자면, 합동 산술은 유클리드 환의 몫의 개념으로 정식화할 수 있다. 이 개념은 동치 관계의 개념에 의해, 많은 대수적 구조에 대해 일반화된다. 환론에서는 아이디얼이 정규 부분군의 역할을 하며, 합동 산술을 포함하는 더 넓은 문맥에서 사용되는 몫환의 개념이 정식화된다.

3.8. 라그랑주의 정리 (정수론)

--
가환환에 계수를 갖는 다항식환은 나눗셈이 가능하므로, 합동 산술을 생각할 수 있다. 갈루아 이론의 출발점은 다항식을 기약 다항식(이것이 수의 경우의 소수에 해당)으로 나눈 합동류의 집합을 체계적으로 다루는 데 있다. 이들 집합은 오늘날 대수적 확대라고 불린다.

3.9. 법 n에 대한 원시근

법 n에 대한 원시근은 n과 서로소인 모든 정수를 거듭제곱으로 표현할 수 있는 수이다.

3.10. 2차 잉여

주어진 원본 소스에는 '2차 잉여'에 대한 직접적인 설명이 없으므로, 요약에 있는 내용은 이 섹션에 포함될 수 없다. 따라서 원본 소스에서 '2차 잉여'와 관련된 내용을 찾을 수 없기 때문에, 이 섹션에는 작성할 내용이 없다.

4. 잉여계

법 m에 대한 잉여류는 m으로 나눈 나머지가 같은 정수들의 집합이다. 예를 들어 m = 5인 경우, 잉여류는 다음과 같이 5개가 존재한다.

* {..., -10, -5, 0, 5, 10, ...}
* {..., -9, -4, 1, 6, 11, ...}
* {..., -8, -3, 2, 7, 12, ...}
* {..., -7, -2, 3, 8, 13, ...}
* {..., -6, -1, 4, 9, 14, ...}

이러한 잉여류들의 집합은 법 m 정수환이라고 하며, $\mathbb{Z}/m\mathbb{Z}$ , $\mathbb{Z}/m$ , 또는 $\mathbb{Z}_m$ 으로 표기한다. 법 m 정수환은 덧셈, 뺄셈, 곱셈 연산에 대해 가환환을 이룬다.

* $\overline{a}_m + \overline{b}_m = \overline{(a + b)}_m$
* $\overline{a}_m - \overline{b}_m = \overline{(a - b)}_m$
* $\overline{a}_m \overline{b}_m = \overline{(a b)}_m$

예를 들어, 24시간제에서 12시 + 21시는 33시가 아니라 9시가 되는 것처럼, $\mathbb{Z}/24\mathbb{Z}$ 에서는 $\overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24}$ 가 된다.

법 m 정수환은 m이 소수일 때 체가 된다.

4.1. 완전 잉여계

법 m에 대한 완전 잉여계는 각 잉여류의 대표를 정확히 하나씩 포함하는 집합이다.

4.2. 최소 잉여계

Modular arithmetic^영어에서, 주어진 정수 m에 대한 모든 합동류의 집합을 법 m 정수환이라고 하며, $\mathbb{Z}/m\mathbb{Z}$ , $\mathbb{Z}/m$ , 또는 $\mathbb{Z}_m$ 로 표기한다. m > 0 에 대해 다음이 성립한다.
: $\mathbb{Z}/m\mathbb{Z} = \left\{ \overline{a}_m \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_m, \overline{1}_m, \overline{2}_m,\ldots, \overline{m{-}1}_m \right\}.$

이때, 집합 {0, 1, 2, ..., m-1}은 최소 잉여계이다.

4.3. 기약 잉여계

오일러 피 함수 $φ(m)$ 가 주어졌을 때, $m$ 과 서로소이고 법 $m$ 에 대해 서로 합동이 아닌 $φ(m)$ 개의 정수의 집합을 법 $m$ 에 대한 기약 잉여계라고 한다. 예를 들어, 집합 $\{5, 15\}$ 는 법 4에 대한 기약 잉여계의 한 예시이다.

5. 아이디얼

Z/(n)에서도 정수환의 경우와 마찬가지로 아이디얼, 소 아이디얼 및 극대 아이디얼의 개념을 정의할 수 있다.

Z/(n)의 아이디얼은 모두 n의 약수에 의하여 생성되는 주 아이디얼이다. 즉, (d) (d|n)의 꼴이다.

이 아이디얼들 가운데, 소 아이디얼인 것은 d가 소수인 경우이다. 즉, Z/(n)의 소 아이디얼은 n의 소인수들의 주 아이디얼들이다. Z/(n)에서 극대 아이디얼의 개념과 소 아이디얼의 개념은 서로 일치한다. 즉, 모든 극대 아이디얼은 소 아이디얼이며, 모든 소 아이디얼은 극대 아이디얼이다.

6. 역사

합동 산술은 고대부터 그 개념이 알려져 있었으나, 19세기 가우스에 의해 체계적으로 정립되었다.

6.1. 유럽의 정수론 발전

--
정수론의 발전에 큰 영향을 준 피에르 드 페르마(1607 - 1665)는 합동 산술의 기초가 되는 잉여를 갖는 나눗셈을 사용했다. 그는 페르마의 대정리, 두 제곱수의 합 정리, 페르마의 소정리 등 여러 정리를 제시했다.

--
18세기 레온하르트 오일러는 페르마가 제시한 문제들을 해결하며, 페르마 수가 항상 소수가 되는 것은 아님을 증명했다. 또한 제곱 잉여의 상호 법칙을 연구했다.

6.2. 가우스의 공헌

19세기 초, 가우스(1777 - 1855)는 이전까지 수학자들이 사용하던 복잡한 방법 대신, 단순한 원리를 도입하여 합동 산술을 체계화했다. 가우스는 1796년 3월 30일에 정십칠각형의 작도 가능성을 증명하였고, 1801년에는 《Disquisitiones Arithmeticae》(『산술 연구』)를 저술하여 수학의 황제라는 별명을 얻었다.

가우스는 정수 계수 다항식을 사용하여 정수 개념을 확장해, 오늘날 가우스 정수라고 불리는 수의 집합을 고안했다. 가우스의 합동 산술은 제곱 잉여의 상호 법칙 증명 등 정수론 발전에 큰 영향을 미쳤다.

6.3. 19세기 이후의 발전

디리클레는 디리클레 지표 개념을 도입하여 해석적 정수론의 기초를 다졌고, 산술 급수 정리를 증명했는데, 이는 합동 산술의 정점으로 평가받는다. 야코비는 디리클레의 업적을 "인류 통찰력의 정점"이라고 평가했다.

이후 합동 산술은 대수적 정수론, 해석적 정수론 등 새로운 분야로 발전해 나갔다.

7. 응용

모듈러 산술은 수론, 군론, 환론, 매듭 이론, 추상대수학 등 순수 수학의 여러 분야와 컴퓨터 대수학, 화학, 시각 및 음악 예술과 같은 응용 수학 분야에서 널리 사용된다.

컴퓨터 대수학에서 모듈러 산술은 중간 계산 및 데이터에서 정수 계수의 크기를 제한하고, 다항식 인수분해, 다항식 최대공약수, 정수 및 유리수에 대한 선형대수, 그뢰브너 기저 알고리즘의 효율적인 구현에 사용되며, 오일러의 거듭제곱 합 추측을 반증하는 데에도 사용되었다.

분수를 모든 밑 b의 순환 소수로 바꿀 때 나눗셈을 사용하는 것은 분모 모듈로 b의 모듈러 곱셈과 같다. 예를 들어 십진법에서는 b = 10이다.

7.1. 암호학

모듈러 산술은 암호학에서 공개 키 시스템(예: RSA, 디피-헬만)의 기초가 되며, 유한체를 제공하여 타원 곡선 암호의 기초가 된다. 또한 고급 암호화 표준(AES), 국제 데이터 암호화 알고리즘(IDEA), RC4 등 다양한 대칭 키 알고리즘에도 사용된다. RSA와 디피-헬만은 모듈러 지수승을 사용한다.

7.2. 정보 이론

모듈러 산술은 오류 검출 및 정정 부호, 체크섬 계산 등에 사용된다. 국제 표준 도서 번호(ISBN), 국제 은행 계좌 번호(IBAN), CAS 등록 번호 등에서 오류 검출을 위해 활용된다.

7.3. 컴퓨터 과학

모듈러 산술은 비트 연산 및 고정 너비, 순환 자료 구조와 관련된 연산에 적용된다. 많은 프로그래밍 언어 및 계산기에서 구현된 모듈로 연산은 이 맥락에서 자주 사용되는 모듈러 산술의 응용이다. 논리 연산자 XOR은 2비트를 모듈로 2로 더한다.

7.4. 기타

음악에서 모듈로 12 산술은 12 평균율 시스템에 사용되며, 옥타브와 이명동음의 동일성이 나타난다. (예: 1:2 또는 2:1 비율의 음은 같고, C-샤프는 D-플랫과 같다고 본다.)

9의 보수 방법은 십진 산술 계산을 빠르게 확인하는 데 사용된다. 이는 모듈로 9의 모듈러 산술과 10 ≡ 1 (mod 9)라는 성질을 이용한다.

모듈로 7 산술은 주어진 날짜의 요일을 구하는 알고리즘에 쓰인다. 특히, 젤러의 합동과 둠스데이 알고리즘은 모듈로 7 산술을 많이 사용한다.

모듈러 산술은 법률 (예: 할당), 경제학 (예: 게임 이론) 등 사회 과학 분야에서도 응용되며, 비례 분할 및 자원 할당이 중요한 부분을 차지한다.

8. 계산 복잡도

선형 합동식 시스템은 가우스 소거법의 한 형태로 다항 시간 안에 풀 수 있으며, 자세한 내용은 선형 합동식 정리를 참조하면 된다. 몽고메리 리덕션과 같은 알고리즘은 곱셈 및 모듈러 {{lang와 같은 간단한 산술 연산을 큰 수에서 효율적으로 수행할 수 있도록 한다.

이산 로그 또는 이차 합동식을 찾는 것과 같은 일부 연산은 정수 인수분해만큼 어려운 것으로 보이며, 따라서 암호학 및 암호화 알고리즘의 시작점이 된다. 이러한 문제는 NP-중간일 수 있다.

비선형 모듈러 산술 방정식을 푸는 것은 NP-완전이다.