나눗셈 정리

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

산술에서, 나머지 있는 나눗셈(영어: division with remainder, Euclidean division)은 두 정수로부터 나머지를 얻는 연산이다. 몫은 나뉘는수에서 나누는수를 (음의 정수가 되기 직전까지) 몇 번 뺄 수 있는지를 나타내는 정수이며, 나머지는 그 횟수만큼 뺀 뒤에 몇이 남는지를 나타내는 정수이다. 나눗셈 정리(영어: division theorem)는 나머지 있는 나눗셈이 0으로 나누기를 제외한 모든 경우에 대하여 정의되었다는 정리이다. 이는 몫과 나머지를 직접 구하는 알고리즘을 알려주지는 않지만, 유클리드 호제법 등에서 응용되는 중요한 정리이다.

정의[편집]

두 정수 ()가 주어졌다고 하자. 나눗셈 정리에 따르면, 다음 조건을 만족시키는 정수 가 유일하게 존재한다.

이 경우, 로 나눈 이라고 하며, 로 나눈 나머지라고 한다. 두 정수의 몫과 나머지를 구하는 연산을 나머지 있는 나눗셈이라고 한다. 나머지가 인 특수한 경우, (즉, 인 경우,) 나누어떨어진다고 하며, 배수, 약수라고 한다. 또한, 이를 로 표기한다.

증명[편집]

존재성[편집]

우선 "몫"과 "나머지"의 존재성부터 증명하자. 인 경우를 증명하는 것으로 족하다. (이는 항등식 때문이다.) 을 고정하고 에 대한 수학적 귀납법을 사용하자. 인 경우,

이므로, (0, 0)은 정리의 조건을 만족시킨다.

이제 의 경우의 가정 아래 의 경우를 증명하자. 가정에 따라, 다음을 만족시키는 두 정수 이 존재한다.

만약 이라면,

이므로, 은 정리를 만족시킨다. 만약 이라면,

이므로, 은 정리를 만족시킨다. 즉, 의 경우가 성립하며, 비슷하게 의 경우 역시 성립한다.

수학적 귀납법에 따라, 임의의 정수 ()에 대하여 정리가 성립하며, 가장 처음의 논증에 따라 의 경우 역시 성립한다. 즉, 존재성이 성립한다.

유일성[편집]

이제 "몫"과 "나머지"의 유일성을 증명하자. 즉, 두 정수 ()에 대하여, 가 모두 정리의 조건

을 만족시킨다고 가정하고 이 두 쌍이 같음()을 증명하자. 위의 조건에 따라

인데, 양변을 로 나눈 뒤 절댓값을 취하면

이므로, 이며, 윗 윗 식에 대입하면 이다. 즉, 유일성이 성립한다.

[편집]

예를 들어 두 정수 13, 4의 나머지 있는 나눗셈은 다음과 같다.

확장[편집]

이 나눗셈 정리는 사실 가우스 정수 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쪽.

바깥 고리[편집]