모듈러 산술 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Clock group.svg|섬네일|시계 속 시간은 법 12에 대한 모듈러 산술을 사용한다. 9시 정각에 4시간을 더하면 1시 정각을 얻는다. 왜냐면 13은 법 12에 대하여 1과 합동이기 때문이다.]]
[[수론]]에서 '''모듈러 산술'''({{llang|en|modular arithmetic}}) 또는 '''합동 산술'''(合同算術)은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. [[정수환]]의 [[몫환]] <math>\mathbb Z/(n)</math>의 [[환 (수학)|환]] 구조로 생각할 수 있다.

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

임의의 두 정수 <math>a,b\in\mathbb Z</math>에 대하여 다음 두 조건이 서로 동치이며, 이 조건이 성립하면 <math>a</math>와 <math>b</math>가 '''법 <math>n</math>에 대하여 합동'''(法<math>n</math>에 對하여 合同, {{llang|en|congruent modulo <math>n</math>}})이라고 한다.
* <math>a=b+kn</math>인 정수 <math>k\in\mathbb Z</math>가 존재한다.
* <math>\phi_n(a)=\phi_n(b)\in\mathbb Z/(n)</math>이다. 즉, <math>a</math>와 <math>b</math>는 <math>\mathbb Z/(n)</math>의 같은 [[동치류]]에 속한다.
이는 기호로는
:<math>a\equiv b\pmod n</math>
이라고 한다. 정수의 합동은 [[동치 관계]]를 이룬다.

== 성질 ==
=== 덧셈 · 뺄셈 · 곱셈 ===
<math>\mathbb Z/(n)</math>은 [[가환환]]이므로, 임의의 가환환에서와 마찬가지로 [[덧셈]] · [[뺄셈]] · [[곱셈]]을 정의할 수 있으며, 덧셈과 곱셈은 [[결합 법칙]] · [[교환 법칙]]을 따르고, 또한 [[분배 법칙]]이 성립한다. <math>\phi_n\colon\mathbb Z\to \mathbb Z/(n)</math>이 [[환 준동형]]이므로, 임의의 <math>a,b,c\in\mathbb Z</math>에 대하여 다음 두 조건이 서로 동치이다.
* <math>ab\equiv c\pmod n</math>
* <math>\phi_n(a)\phi_n(b)=\phi_n(c)</math>
마찬가지로, 다음 두 조건이 서로 동치이다.
* <math>a+b\equiv c\pmod n</math>
* <math>\phi_n(a)+\phi_n(b)=\phi_n(c)</math>
마찬가지로, 다음 두 조건이 서로 동치이다.
* <math>a\equiv-b\pmod n</math>
* <math>\phi_n(a)=-\phi_n(b)</math>

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

=== 나눗셈 ===
일반적으로, <math>\mathbb Z/(n)</math>은 [[체 (수학)|체]]가 아니므로, 모듈러 산술에서 나눗셈은 일반적으로 정의되지 않는다. 다만, 만약 <math>n</math>이 [[소수 (수론)|소수]]라면 <math>\mathbb Z/(n)</math>은 [[체 (수학)|체]]를 이루며, 이 경우 0이 아닌 모든 수의 역수가 존재한다.

합성수 <math>n</math>에 대한 모듈러 산술의 경우, 오직 <math>n</math>과 [[서로소 정수|서로소]]인 수만이 [[가역원]]이다 (역수를 정의할 수 있다). 이는 [[오일러의 정리]]에 따라
:<math>a^{\phi(n)}\equiv1\pmod n</math>
이기 때문이다 (<math>\phi</math>는 [[오일러 피 함수]]). 즉, <math>n</math>개의 합동류 가운데 오직 <math>\phi(n)</math>개만이 [[가역원]]이며, 가역원 <math>a</math>의 역원은 <math>a^{\phi(n)-1}</math>이다.

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

==== 2의 거듭제곱 ====
<math>k>1</math>에 대하여, <math>\mathbb Z/(2^k)</math>의 가역원군은 다음과 같다.
:<math>(\mathbb Z/(2^k))^\times\cong Z_2\times Z_{2^{k-2}}</math>

==== 일반적 합성수 ====
일반적 합성수의 경우, 가역원군은 [[중국인의 나머지 정리]]에 따라서
:<math>\left(\mathbb Z/\left(\prod_pp^{n_p}\right)\right)^\times\cong\prod_p(\mathbb Z/(p^{n_p}))^\times</math>
이다.

=== 아이디얼 ===
<math>\mathbb Z/(n)</math>에서도 정수환의 경우와 마찬가지로 [[아이디얼]]과 [[소 아이디얼]] 및 [[극대 아이디얼]]의 개념을 정의할 수 있다.
<math>\mathbb Z/(n)</math>의 아이디얼은 모두 <math>n</math>의 약수에 의하여 생성되는 [[주 아이디얼]]이다. 즉, <math>(d)</math> (<math>d\mid n</math>)의 꼴이다.

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

따라서, <math>\mathbb Z/(n)</math>의 [[크룰 차원]]은 다음과 같다.
:<math>\dim\mathbb Z/(n)=\begin{cases}1&n=0\\-\infty&n=1\\0&n\ne0,1\end{cases}</math>
이는 [[대수기하학]]적으로 다음과 같이 해석할 수 있다. <math>n</math>의 [[소인수 분해]]가
:<math>n=\prod_{i=1}^kp_i^{n_i}</math>
라면, [[중국인의 나머지 정리]]에 따라서
<math>\mathbb Z/(n)\cong\prod_{i=1}^k\mathbb Z/(p_i^{n_i})</math>
이다. 이는 [[가환환]]의 범주에서의 [[곱 (범주론)|곱]]이므로, [[아핀 스킴]]의 범주에서의 [[쌍대곱]]이 된다. 즉,
:<math>\operatorname{Spec}\mathbb Z/(n)=\bigsqcup_{i=1}^k\operatorname{Spec}\mathbb Z/(p_i^{n_i})</math>
가 된다. 각 <math>\mathbb Z/(p_i^{n_i})</math>는 하나의 [[소 아이디얼]] <math>(p_i)</math>을 갖는 [[국소환]]이며, 따라서 [[위상 공간 (수학)|위상 공간]]으로서는 [[한원소 집합]]이다. 즉, [[아핀 스킴]] <math>\operatorname{Spec}\mathbb Z/(n)</math>은 위상 공간으로서 <math>n</math>의 각 소인수에 대응하는 <math>k</math>개의 점들로 구성된 공간이다.

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

== 예 ==
14와 20 그리고 −4는 법 6에 대하여 합동이다. 이를 식으로 나타내면
:<math>14 \equiv 20 \equiv -4 \pmod{6}</math>
이다.

== 같이 보기 ==
* [[중국인의 나머지 정리]]

== 외부 링크 ==
* {{eom|title=Congruence}}
* {{eom|title=Congruence equation}}
* {{eom|title=Two-term congruence}}
* {{eom|title=Congruence modulo a prime number}}
* {{매스월드|id=Congruence|title=Congruence}}
* {{매스월드|id=CongruenceEquation|title=Congruence equation}}

[[분류:모듈러 산술| ]]
[[분류:수론]]
[[분류:가환대수학]]
[[분류:유한환]]