나눗셈 정리

대체글=한 줄에 5개씩 나열하여 마지막 줄에 2개가 남은 총 17개의 원|섬네일|. 17개를 한 줄에 5개씩 나열하면 3줄에 2개가 남는다.
대체글=아홉 조각의 파이를 두 조각씩 나눠 먹는 네 사람|섬네일|. 9조각의 파이를 4명의 사람이 2조각씩 나눠 먹으면 1조각이 남는다.
수학에서 나눗셈 정리(-定理, )는 임의의 정수를 0이 아닌 정수로 나눈 몫과 나머지를 유일하게 정의할 수 있다는 정리이다. 두 정수로부터 몫과 나머지를 얻는 연산을 나머지 있는 나눗셈() 또는 유클리드 나눗셈()이라고 한다. 양의 정수를 양의 정수로 나눈 몫은 나뉘는 수가 음의 정수가 되기 직전까지 나누는 수를 뺀 횟수를 나타내며, 나머지는 이 횟수만큼 뺀 차를 나타낸다. 예를 들어, 17에서 5를 3번 빼면 2가 남으며, 3번 이상 빼면 음의 정수가 되므로, 17를 5로 나눈 몫은 3이며 나머지는 2이다. 이를 곱셈을 사용하여 표기하면 다음과 같다.

일반적인 두 정수의 나머지 있는 나눗셈에서 나머지는 나누는 수 의 절댓값보다 작은 음이 아닌 정수들 가운데 하나이다. 각각 와 법 에 대하여 합동인 정수들

을 얻는다. 즉, 이며, 따라서 이다. 이에 따라, 정리 속 조건을 만족시키는 는 유일하다.

 예 
을 으로 나눈 몫은 , 나머지는 이다 ().

 따름정리 
 대분수 전개 
모든 유리수는 정수와 분모가 양의 정수인 기약 진분수의 합으로 유일하게 나타낼 수 있다. 즉, 유리수 (는 정수, , 와 는 서로소)에 대하여, 를 로 나눈 몫과 나머지를 각각 라고 하면,

이며, 이 경우 는 기약 분수이자 진분수이다.

 다항식 나눗셈 정리 
 정의 
환 에서 계수를 취하는 두 다항식 가 주어졌고, 이며, 의 최고차항의 계수가 의 가역원이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 가 유일하게 존재한다.
 
 
마찬가지로, 다음 두 조건을 만족시키는 다항식 가 유일하게 존재한다.
 
 
여기서 는 다항식의 차수이다 (). 특히, 가 일계수 다항식일 경우 나눗셈 정리가 적용된다 (은 항상 가역원이기 때문이다). 만약 가 가환환일 경우, 역시 가환환이므로, 는 와 일치한다. 만약 가 나눗셈환일 경우, 의 모든 0이 아닌 원소는 가역원이므로, 나눗셈 정리는 임의의 에 대하여 성립한다.

우선 가 존재함을 증명하자. 임의의 을 고정하고 에 대한 수학적 귀납법을 사용하자. 만약 라면, 과 를 취하면 된다. 이제, 라고 하고, 차수가 보다 낮은 다항식이 항상 로 나눈 몫과 나머지를 갖는다고 가정하자. 차수 에 대한 수학적 귀납법을 사용하자.

라고 하고,

라고 하자. 그렇다면 이므로, 수학적 귀납법의 가정에 의하여 다음 두 조건을 만족시키는 가 존재한다.
 
 
그렇다면

와 는 원하는 조건을 만족시킨다.

이제 가 유일함을 증명하자. 가 다음 조건을 만족시킨다고 가정하자.
 
 
 
그렇다면

이며, 또한 의 최고차항의 계수는 왼쪽 또는 오른쪽 영인자가 아니므로,

이다. 따라서 , 이다.

보다 일반적으로, 환 에서 계수를 취하는 다항식 가 주어졌고, 이며, 의 최고차항의 계수를 라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 가 존재한다.
 
 
마찬가지로, 다음 두 조건을 만족시키는 다항식 가 존재한다.
 
 
만약 가 가역원이라면, 이러한 는 유일하다.

 체의 경우 
만약 가 나눗셈환일 경우, 의 모든 0이 아닌 원소는 가역원이므로, 임의의 의 최고 차수의 항의 계수는 가역원이다. 특히 만약 가 체라면, 는 가환환이며, 두 종류의 나눗셈을 구분할 필요가 없다. 체 계수의 다항식의 나눗셈 정리는 다음과 같다.

체 에서 계수를 취하는 다항식 가 주어졌고, 이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 가 유일하게 존재한다.
 
 
이에 따라, 체에 대한 일변수 다항식환 는 유클리드 정역을 이룬다.

 복소수 계수 다항식의 경우 
실수체에 대한 다항식 나눗셈 정리에 따라, 실수 계수 다항식을 실수 계수 다항식으로 나눈 몫과 나머지는 실수 계수 다항식이다. 유리수 계수 다항식도 마찬가지다. 정수환에 대한 다항식 나눗셈 정리에 따라, 정수 계수 다항식을 정수 계수 일계수 다항식으로 나눈 몫과 나머지는 항상 정수 계수 다항식이다. 그러나 일반적으로 정수 계수 다항식의 나눗셈에서의 몫과 나머지는 유리수 계수 다항식이며, 이는 정수 계수 다항식이 아닐 수 있다.

 예 
정수 계수 다항식 를 로 나눈 몫과 나머지는 각각 와 이다.

임의의 환 에서, 다항식 를 (는 가역원)로 나눈 몫은 , 나머지는 0이다. 그 반대환 에서 몫과 나머지는 각각 와 0이다. 가 가환환일 경우 반대환은 자기 자신과 일치하므로, 와 에서의 몫과 나머지는 일치한다.

 따름정리 
 나머지 정리 

환 에서 계수를 취하는 다항식 가 주어졌고, 를 부분환으로 갖는 환 의 원소 가 의 모든 원소와 가환한다고 하자 (임의의 에 대하여, ). 나머지 정리(-定理, )에 따르면, 를 로 나눈 나머지는 이다.

특히, 만약 가 가환환일 경우, 임의의 에 대하여 나머지 정리가 성립한다.

다항식 나눗셈 정리에 따라 다음 두 조건을 만족시키는 가 존재한다.
 
 
따라서 이다. 함수

는 자명하게 덧셈을 보존한다. 또한, 가 의 모든 원소와 가환하므로 이는 곱셈을 보존한다. 즉, 환 준동형이다. 이를

에 적용하면

을 얻는다.

 인수 정리 

환 에서 계수를 취하는 다항식 가 주어졌고, 를 부분환으로 갖는 환 의 원소 가 의 모든 원소와 가환한다고 하자 (임의의 에 대하여, ). 인수 정리(因數定理, )에 따르면, 다음 두 조건이 서로 동치이다.
 
 
특히, 만약 가 가환환일 경우 이는 임의의 에 대하여 성립한다.

만약 라면, 인 가 존재하므로,

이다.

만약 이라면, 나머지 정리에 따라

인 가 존재하므로 이다.

 대분수 전개 
체 에서 계수를 취하는 유리 함수는 다음과 같은 꼴로 유일하게 나타낼 수 있다.

여기서 다항식 는 다음 조건을 만족시킨다.
 
 는 일계수 다항식이다.
 

 g진 전개 
환 에서 계수를 취하는 두 다항식 가 주어졌고, , 이며, 의 최고차항의 계수가 의 가역원이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 가 유일하게 존재한다.
 
 
마찬가지로, 다음 두 조건을 만족시키는 다항식 가 유일하게 존재한다.
 
 
여기서 는 바닥 함수이다. 특히, 일 경우 이는 다항식 의 통상적인 전개와 같다.

 알고리즘 
다항식의 나머지 있는 나눗셈의 몫과 나머지를 구하는 방법으로 장제법이 있다. 만약 1차 다항식으로 나눌 경우 조립제법을 사용할 수 있다. 다항식 나머지 정리에 따라, 다항식의 정의역 속 원소에 대한 값은 조립제법을 통해 구할 수 있다. 이는 다항식의 통상적인 전개를 통한 계산보다 덜 복잡하다.

 유클리드 정역 

 정의 
정수환 또는 체 위의 다항식환 와 같이, 나머지 있는 나눗셈을 할 수 있고 정역을 이루는 환을 유클리드 정역이라고 한다. 구체적으로, 유클리드 정역은 다음을 만족시키는 함수 가 존재하는 정역 이다.
 임의의 ()에 대하여, 이며, 이거나 인 이 존재한다.
이 경우 는 정수환이나 다항식환에서와 달리 유일하지 않을 수 있다.

 예 
정수환 은 절댓값 함수 에 대하여 유클리드 정역을 이룬다. 체 위의 다항식환 는 차수 함수 에 대하여 유클리드 정역을 이룬다.

주 아이디얼 정역은 유클리드 정역보다 약한 조건이다. 즉, 유클리드 정역의 모든 아이디얼은 한 원소로 생성할 수 있지만, 그 역은 성립하지 않는다. 예를 들어, 의 아이디얼은 음이 아닌 정수 을 통해 의 꼴로 유일하게 나타낼 수 있으며, 의 아이디얼은 유일한 일계수 다항식 또는 0을 생성원으로 갖는다.

이차 수체의 대수적 정수환은 유클리드 정역을 이룰 필요가 없다. 유클리드 정역을 이루는 허수 이차 수체의 대수적 정수환은 유한 개밖에 없으며, 이들은 모두 체 노름에 대하여 유클리드 정역을 이룬다. 체 노름의 절댓값에 대하여 유클리드 정역을 이루는 실수 이차 수체의 대수적 정수환도 유한 개뿐이다. 다음은 유클리드 정역을 이루는 이차 수체의 대수적 정수환의 일부이다.

 가우스 정수환 
허수 이차 수체 의 대수적 정수환

를 가우스 정수환이라고 한다. 위의 체 노름은

이며, 가우스 정수환은 체 노름에 대하여 유클리드 정역을 이룬다.

임의의 (, )에 대하여,

라고 하자. 이제,

인 를 취하고

라고 하자. 그렇다면,

이다. 이에 따라 는 체 노름 에 대하여 유클리드 정역을 이룬다.

가우스 정수환의 원소는 데카르트 좌표 평면 위의 격자점, 또는 원점에서 격자점을 향하는 벡터와 일대일 대응하며, 체 노름은 원점과의 거리의 제곱과 같다. 의 배 에 대응하는 벡터는 에 대응하는 벡터와 직교한다. 따라서, 의 배수는 와 의 정수 계수 선형 결합이므로, 와 를 기저로 하는 새로운 데카르트 좌표계의 격자점에 대응한다. 주어진 에 대하여, 새로운 격자점들 가운데 와 가장 가까운 하나를 라고 하자. 그렇다면 를 에서 로 나눈 몫으로 취할 수 있다. 이 경우 나머지 는 에서 를 향하는 벡터와 같다.

 −3에 대한 이차 수체의 대수적 정수환 
허수 이차 수체 의 대수적 정수환

은 체 노름

에 대하여 유클리드 정역을 이룬다.

임의의 (, )에 대하여,

라고 하자. 이제,

인 를 취하고,

이라고 하자. 그렇다면,

이다. 이에 따라 은 체 노름 에 대하여 유클리드 정역을 이룬다.

 다변수 다항식 

 정의 
 단항식 순서 

체 가 주어졌다고 하자. 일변수 다항식환 속에서 표준적인 나눗셈을 정의할 수 있는 것은 단항식들 사이에 표준적인 순서 가 존재하기 때문이다. 다변수 다항식환 의 단항식들 사이에는 표준적인 순서가 존재하지 않으며, 다변수 다항식들의 나눗셈을 정의하기 위해서는 단항식 순서를 미리 지정해야 한다.

체 에서 계수를 취하는 다변수 다항식환 위의 단항식 순서(單項式順序, )는 다음 세 조건을 만족시키는, 단항식의 집합 위의 전순서 이다.
 만약 이라면, 이다.
 항상 이다.
 는 정렬 전순서이다.
두 번째와 세 번째 조건은 하나만 취하여도 좋다. 첫 번째와 두 번째 조건은 세 번째 조건을 함의하며, 반대로 첫 번째와 세 번째 조건도 두 번째 조건을 함의하기 때문이다. 정의에 따라, 만약 이라면, 이다.

체 에서 계수를 취하는 다변수 다항식환 위의 단항식 순서 가 주어졌다고 하자. 그렇다면, 임의의 다변수 다항식 은 그 (0이 아닌) 항들을 에 대하여 큰 항부터 작은 항까지의 순서대로 정렬하여

꼴로 나타낼 수 있다. 이 경우, 단항식 순서 에 대한 의 최고차항(最高次項, )과 최고차 계수(最高次係數, )와 최고차 단항식(最高次單項式, )은 각각 다음과 같다.

(다항식 0의 최고차항, 최고차 계수, 최고차 단항식은 보통 모두 0으로 정의하며, 항상 이라고 생각한다.)

 다변수 나눗셈 

체 에서 계수를 취하는 다변수 다항식 및 단항식 순서 가 주어졌고, 이라고 하자. 그렇다면, 다음을 만족시키는 다변수 다항식 이 존재한다.
 
 
 
 에 등장하는 모든 (0이 아닌 계수의) 단항식은 의 배수가 아니다.
이 경우 몫과 나머지 는 유일할 필요가 없다. 만약 가 의 그뢰브너 기저를 이룰 경우, 나머지 는 항상 유일하며, 임의의 에 대하여, 다음 두 조건이 서로 동치이다.
 
 를 로 나눈 나머지는 0이다.

 그뢰브너 기저 

체 에서 계수를 취하는 다변수 다항식환 의 아이디얼 및 단항식 순서 가 주어졌다고 하자. 유한 집합 에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 를 의 그뢰브너 기저라고 한다.
 
 임의의 에 대하여, 인 가 존재한다.
 임의의 에 대하여, 를 로 나눈 모든 나머지는 0이다.
 임의의 에 대하여, 를 로 나눈 나머지 가운데 적어도 하나는 0이다.
 (부흐베르거 알고리즘) 이며, 임의의 에 대하여, 를 로 나눈 모든 나머지는 0이다.
 (부흐베르거 알고리즘) 이며, 임의의 에 대하여, 를 로 나눈 나머지 가운데 적어도 하나는 0이다.
여기서, 임의의 다항식 집합 에 대하여, 는 로 생성된 의 아이디얼이다. 가 유한 집합일 경우 는 로 표기할 수 있다. 또한,

이다. 은 최소 공배수를 뜻한다.

아이디얼 의 그뢰브너 기저는 항상 존재한다. 모든 (무한 집합일 수 있는) 그뢰브너 기저는 유한 부분 그뢰브너 기저를 가지므로, 유한하지 않은 크기의 그뢰브너 기저는 다룰 필요가 없다.

 부흐베르거 알고리즘 

체 에서 계수를 취하는 유한 개의 다변수 다항식 으로 생성된 아이디얼 의 그뢰브너 기저는 다음과 같은 과정을 통해 찾을 수 있으며, 이를 부흐베르거 알고리즘()이라고 한다.
 에서 시작한다.
 각 에 대하여, 를 로 나눈 나머지 를 구하되, 0이 아닌 나머지 을 발견했거나, 모든 에 대하여 구했다면 멈춘다.
 만약 0이 아닌 나머지 을 발견했다면, 을 의 새로운 원소로 추가하여 2번째 단계를 반복한다. 만약 임의의 에 대하여 이라면, 는 의 그뢰브너 기저이다.

 같이 보기 
 유클리드의 보조 정리
 유클리드 호제법
 각주 

 외부 링크 
 

분류:수론 정리
분류:환론
분류:나눗셈