모듈러 산술: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
1번째 줄:
{{다른 뜻|합동|[[
[[
:<math>a \equiv b \pmod{m} </math> <br />▼
== 정의 ==
<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>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>\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)}\cong1\pmod n</math>
이기 때문이다 (<math>\phi</math>는 [[오일러 피 함수]]). 즉, <math>n</math>개의 합동류 가운데 오직 <math>\phi(n)</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>
이다.
== 예 ==
줄 18 ⟶ 65:
[[분류:수론]]
| |||