나눗셈 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
한 줄에 5개씩 나열하여 마지막 줄에 2개가 남은 총 17개의 원
17개를 5개씩 묶으면 3묶음에 2개가 남는다. 이는 나뉘는수가 17, 나누는수가 5인 나머지 있는 나눗셈이며, 몫은 3, 나머지는 2이다. 즉, 17 = 5 × 3 + 2.
아홉 조각의 파이를 두 조각씩 나눠 먹는 네 사람
9조각의 파이와 4명의 사람이 있을 때, 2조각씩 나눠 먹으면 1조각이 남는다.

산술에서, 나머지 있는 나눗셈(영어: division with remainder, Euclidean division)은 두 정수로부터 나머지를 얻는 연산이다. 몫은 나뉘는수에서 나누는수를 (음의 정수가 되기 직전까지) 몇 번 뺄 수 있는지를 나타내는 정수이며, 나머지는 그 횟수만큼 뺀 뒤에 몇이 남는지를 나타내는 정수이다. 나눗셈 정리(영어: division theorem)는 나머지 있는 나눗셈이 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쪽.

외부 링크[편집]