모듈러 산술

시계 속 시간은 법 12에 대한 모듈러 산술을 사용한다. 9시 정각에 4시간을 더하면 1시 정각을 얻는다. 왜냐면 13은 법 12에 대하여 1과 합동이기 때문이다.

수론에서 모듈러 산술(영어: modular arithmetic) 또는 합동 산술(合同算術)은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 정수환의 몫환 $ℤ / (n)$ 의 환 구조로 생각할 수 있다.

정의

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

ϕ_{n} : ℤ \to ℤ / (n)

을, 정수를 $n$ 에 대한 나머지로 대응시키는 함수로 여길 수 있다.

임의의 두 정수 $a, b \in ℤ$ 에 대하여 다음 두 조건이 서로 동치이며, 이 조건이 성립하면 $a$ 와 $b$ 가 법 $n$ 에 대하여 합동(法 $n$ 에 對하여 合同, 영어: congruent modulo $n$ )이라고 한다.

$a = b + k n$ 인 정수 $k \in ℤ$ 가 존재한다.
$ϕ_{n} (a) = ϕ_{n} (b) \in ℤ / (n)$ 이다. 즉, $a$ 와 $b$ 는 $ℤ / (n)$ 의 같은 동치류에 속한다.

이는 기호로는

a \equiv b (\mod n)

이라고 한다. 정수의 합동은 동치 관계를 이룬다.

성질

덧셈 · 뺄셈 · 곱셈

$ℤ / (n)$ 은 가환환이므로, 임의의 가환환에서와 마찬가지로 덧셈 · 뺄셈 · 곱셈을 정의할 수 있으며, 덧셈과 곱셈은 결합 법칙 · 교환 법칙을 따르고, 또한 분배 법칙이 성립한다. $ϕ_{n} : ℤ \to ℤ / (n)$ 이 환 준동형이므로, 임의의 $a, b, c \in ℤ$ 에 대하여 다음 두 조건이 서로 동치이다.

$a b \equiv c (\mod n)$
$ϕ_{n} (a) ϕ_{n} (b) = ϕ_{n} (c)$

마찬가지로, 다음 두 조건이 서로 동치이다.

$a + b \equiv c (\mod n)$
$ϕ_{n} (a) + ϕ_{n} (b) = ϕ_{n} (c)$

마찬가지로, 다음 두 조건이 서로 동치이다.

$a \equiv - b (\mod n)$
$ϕ_{n} (a) = - ϕ_{n} (b)$

중국인의 나머지 정리

$n$ 의 소인수 분해가

n = \prod_{p} p^{n_{p}}

라고 하자. 그렇다면 중국인의 나머지 정리에 따르면 다음과 같은 가환환의 동형이 존재한다.

ℤ / (n) ≅ \prod_{p} ℤ / (p^{n_{p}})

즉, 두 개 이상의 소인수를 갖는 수에 대한 모듈러 산술은 그 소인수들(의 거듭제곱)에 대한 합동류들을 성분별로 취급하는 것과 같다.

나눗셈

일반적으로, $ℤ / (n)$ 은 체가 아니므로, 모듈러 산술에서 나눗셈은 일반적으로 정의되지 않는다. 다만, 만약 $n$ 이 소수라면 $ℤ / (n)$ 은 체를 이루며, 이 경우 0이 아닌 모든 수의 역수가 존재한다.

합성수 $n$ 에 대한 모듈러 산술의 경우, 오직 $n$ 과 서로소인 수만이 가역원이다 (역수를 정의할 수 있다). 이는 오일러의 정리에 따라

a^{ϕ (n)} \equiv 1 (\mod n)

이기 때문이다 ( $ϕ$ 는 오일러 피 함수). 즉, $n$ 개의 합동류 가운데 오직 $ϕ (n)$ 개만이 가역원이며, 가역원 $a$ 의 역원은 $a^{ϕ (n) - 1}$ 이다.

홀수 소수의 거듭제곱

2가 아닌 소수 $p$ 에 대하여, $ℤ / (p^{k})$ 의 가역원들은 총

ϕ (p^{k}) = p^{k - 1} (p - 1)

개가 있으며 ( $ϕ$ 는 오일러 피 함수), 그 가역원군은 순환군이다.

(ℤ / (p^{k}))^{\times} ≅ Z_{ϕ (p^{k})}

2의 거듭제곱

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

(ℤ / (2^{k}))^{\times} ≅ Z_{2} \times Z_{2^{k - 2}}

일반적 합성수

일반적 합성수의 경우, 가역원군은 중국인의 나머지 정리에 따라서

{(ℤ / (\prod_{p} p^{n_{p}}))}^{\times} ≅ \prod_{p} (ℤ / (p^{n_{p}}))^{\times}

이다.

아이디얼

$ℤ / (n)$ 에서도 정수환의 경우와 마찬가지로 아이디얼과 소 아이디얼 및 극대 아이디얼의 개념을 정의할 수 있다. $ℤ / (n)$ 의 아이디얼은 모두 $n$ 의 약수에 의하여 생성되는 주 아이디얼이다. 즉, $(d)$ ( $d ∣ n$ )의 꼴이다.

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

따라서, $ℤ / (n)$ 의 크룰 차원은 다음과 같다.

\dim ℤ / (n) = {\begin{matrix} 1 & n = 0 \\ - \infty & n = 1 \\ 0 & n \neq 0, 1 \end{matrix}

이는 대수기하학적으로 다음과 같이 해석할 수 있다. $n$ 의 소인수 분해가

n = \prod_{i = 1}^{k} p_{i}^{n_{i}}

라면, 중국인의 나머지 정리에 따라서 $ℤ / (n) ≅ \prod_{i = 1}^{k} ℤ / (p_{i}^{n_{i}})$ 이다. 이는 가환환의 범주에서의 곱이므로, 아핀 스킴의 범주에서의 쌍대곱이 된다. 즉,

Spec ℤ / (n) = ⨆_{i = 1}^{k} Spec ℤ / (p_{i}^{n_{i}})

가 된다. 각 $ℤ / (p_{i}^{n_{i}})$ 는 하나의 소 아이디얼 $(p_{i})$ 을 갖는 국소환이며, 따라서 위상 공간으로서는 한원소 집합이다. 즉, 아핀 스킴 $Spec ℤ / (n)$ 은 위상 공간으로서 $n$ 의 각 소인수에 대응하는 $k$ 개의 점들로 구성된 공간이다.

(만약 $n = 0$ 일 경우, 이는 정수환의 스펙트럼이므로, 1차원이다. $n = 1$ 일 경우, 자명환의 스펙트럼은 공집합이다.)

예

14와 20 그리고 −4는 법 6에 대하여 합동이다. 이를 식으로 나타내면

14 \equiv 20 \equiv - 4 (\mod 6)

이다.

같이 보기

중국인의 나머지 정리

외부 링크

“Congruence” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
“Congruence equation” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
“Two-term congruence” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
“Congruence modulo a prime number” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Congruence” (영어). 《Wolfram MathWorld》. Wolfram Research.
Weisstein, Eric Wolfgang. “Congruence equation” (영어). 《Wolfram MathWorld》. Wolfram Research.