합동 산술

위키백과, 우리 모두의 백과사전.
(합동 (대수학)에서 넘어옴)
이동: 둘러보기, 검색

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

정의[편집]

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에 대하여 다음 두 조건이 서로 동치이며, 이 조건이 성립하면 abn에 대하여 합동(法n에 對하여 合同, 영어: congruent modulo n)이라고 한다.

  • a=b+kn인 정수 k\in\mathbb Z가 존재한다.
  • \phi_n(a)=\phi_n(b)\in\mathbb Z/(n)이다. 즉, ab\mathbb Z/(n)의 같은 동치류에 속한다.

이는 기호로는

a\equiv b\pmod n

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

성질[편집]

덧셈 · 뺄셈 · 곱셈[편집]

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

  • ab\equiv c\pmod n
  • \phi_n(a)\phi_n(b)=\phi_n(c)

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

  • a+b\equiv c\pmod n
  • \phi_n(a)+\phi_n(b)=\phi_n(c)

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

  • a\equiv-b\pmod n
  • \phi_n(a)=\phi_n(-b)

중국인의 나머지 정리[편집]

n소인수 분해

n=\prod_pp^{n_p}

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

\mathbb Z/(n)\cong\prod_p(\mathbb Z/(p^{n_p})

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

나눗셈[편집]

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

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

a^{\phi(n)}\cong1\pmod n

이기 때문이다 (\phi오일러 피 함수). 즉, n개의 합동류 가운데 오직 \phi(n)개만이 가역원이다.

홀수 소수의 거듭제곱[편집]

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)}

2의 거듭제곱[편집]

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

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

일반적 합성수[편집]

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

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

이다.

[편집]

14와 20은 법 6에 대하여 합동이다. 이를 식으로 나타내면

14 \equiv 20 \pmod{6}

이다.

바깥 고리[편집]