나눗셈 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

정수론에서, 나눗셈 정리(division algorithm)는 두 정수나눗셈에서 나머지에 관한 정리이다. 몫과 나머지를 직접적으로 알려 주지는 않지만, 최대공약수의 성질이나 유클리드 호제법 등에도 사용되는 중요한 정리이다.

정리[편집]

임의의 양의 정수 a와 정수 b에 대해서 다음 식을 만족하는 q와 r이 유일하게 존재한다.

 b=qa+r\ (0\le r<a)

이 때 q를 b를 a로 나눈 , r을 b를 a로 나눈 나머지라 한다. 또, r=0일 때 a는 b를 나눈다고 하고 기호로

 a|b

로 나타낸다. 이 때, a를 b의 약수, b를 a의 배수라고 한다.

  • 예를 들어 두 정수가 13, 4일때, 다음과 같이 나타낼수 있다.
13=3*4+1

증명[편집]

다음과 같은 집합 S를 생각하자.

S=\{b-na|n\in\mathbb{Z},\;b-na\ge0\}

이 때, 정수의 정렬 원리에 의해 집합 S의 가장 작은 원소 r이 존재한다. r은 S의 원소이므로 적당한 정수 q에 대해서 r=b-qa로 표시 할 수 있다. 따라서,

b=qa+r,\ r\ge0

만약, r≥a라 가정하면 b-(q+1)a=r-a\ge0 이므로 b-(q+1)a\in S 이다. 이는 r이 S의 가장 작은 원소라는 사실에 모순이다. 따라서,

r<a

이다. 이제 q, r의 유일성을 보이자.

정수 q_1,\,r_1b=q_1 a+r_1\;(0\le r_1<a) 을 만족시킨다고 하자.

그러면 (q_1-q)a=r-r_1 이다.

만약, q_1\ne q라 하면,

\left|a\right|\le\left|q_1-q\right|\left|a\right|=\left|(q_1-q)a\right|=\left|r-r_1\right|<\left|a\right|

가 되어 모순이다. 그러므로 q_1=q,\;r_1=r 이다.

따라서, q와 r은 유일하게 존재한다.

확장[편집]

이 나눗셈 정리는 사실 가우스 정수 Z[i] := {a + bi|a, b∈Z}에서도 성립한다. 구체적으로 말해,

  • 가우스 정수 a, b에 대하여, a = bq + r이고 |r| < |b|를 만족하는 가우스 정수 q, r이 존재한다.

보다 일반적으로, 정역 중 나눗셈 정리의 위 조건과, 가우스 정수에서 성립하는 다음 조건,

  • 가우스 정수 a, b에 대하여 a≠0이면 |b| ≤ |ab|이다.

의 둘을 만족하는 형태의 절댓값 함수가 존재하는 것을 유클리드 정역(ED)이라 한다. 정수환의 확장에서 이러한 함수는 노름(norm)이라 불리는데, 위의 Z[i] 및 Z[√-2], Z[√2], Z[√3]은 모두 유클리드 정역이다. 임의의 는 유클리드 정역이며, 유클리드 정역은 주 아이디얼 정역(PID)이다.[1][2]

주석[편집]

  1. Joseph A. Gallian (2006), Contemporary Abstract Algebra, Houghton Mifflin Company(Boston, New York), pp.329-331.
  2. 김응태, 박승안, 《현대대수학》, 경문사, 2008, 542-543쪽.

같이 보기[편집]