나눗셈 정리

대체글=한 줄에 5개씩 나열하여 마지막 줄에 2개가 남은 총 17개의 원|섬네일|<math>17=5\times 3+2</math>. 17개를 한 줄에 5개씩 나열하면 3줄에 2개가 남는다.
대체글=아홉 조각의 파이를 두 조각씩 나눠 먹는 네 사람|섬네일|<math>9=4\times 2+1</math>. 9조각의 파이를 4명의 사람이 2조각씩 나눠 먹으면 1조각이 남는다.
수학에서 **나눗셈 정리**(-定理, )는 임의의 정수를 0이 아닌 정수로 나눈 몫과 나머지를 유일하게 정의할 수 있다는 정리이다. 두 정수로부터 몫과 나머지를 얻는 연산을 **나머지 있는 나눗셈**() 또는 **유클리드 나눗셈**()이라고 한다. 양의 정수를 양의 정수로 나눈 몫은 나뉘는 수가 음의 정수가 되기 직전까지 나누는 수를 뺀 횟수를 나타내며, 나머지는 이 횟수만큼 뺀 차를 나타낸다. 예를 들어, 17에서 5를 3번 빼면 2가 남으며, 3번 이상 빼면 음의 정수가 되므로, 17를 5로 나눈 몫은 3이며 나머지는 2이다. 이를 곱셈을 사용하여 표기하면 다음과 같다.
:17=5\times 3+2
일반적인 두 정수의 나머지 있는 나눗셈에서 나머지는 나누는 수 n의 절댓값보다 작은 음이 아닌 정수들 0,1,\dots,|n|-1 가운데 하나이다. 각각 0,1,\dots,|n|-1와 법 n에 대하여 합동인 정수들
:a_0,a_1,\dots,a_{|n|-1}\qquad(a_k\equiv k\pmod n)
역시 나머지의 범위로 삼을 수 있다.

임의의 다항식을 0이 아닌 다항식으로 나눈 몫과 나머지 역시 유일하게 정의할 수 있다. 다항식의 나머지 있는 나눗셈은 나뉘는 다항식에서 나누는 다항식의 적절한 배수를 빼 차수가 나누는 다항식보다 낮은 다항식이 남도록 만드는 연산이다. 예를 들어, f(x)=x^3-x+2를 g(x)=x^2+1로 나눌 경우,
:f(x)=xg(x)-2x+2
이며, 1차 다항식 -2x+2는 2차 다항식 g(x)보다 차수가 낮으므로, 몫은 q(x)=x이며 나머지는 r(x)=-2x+2이다.

정수환이나 다항식환과 같이 나눗셈 정리와 유사한 성질이 성립하는 환을 유클리드 정역이라고 한다. 유클리드 정역에서의 몫과 나머지는 유일하게 정의되지 않을 수 있다. 정수환과 다항식환 이외에도 가우스 정수환은 절댓값에 대하여 유클리드 정역을 이룬다.

일변수 다항식의 나머지 있는 나눗셈은 다변수 다항식에까지 일반화할 수 있다. 즉, 임의의 다변수 다항식을 여러 개의 0이 아닌 다변수 다항식으로 나눈 몫과 나머지를 생각할 수 있다. 이 경우 몫과 나머지는 일반적으로 유일하지 않지만, 나누는 다항식들이 그뢰브너 기저를 이룰 경우 유일한 나머지를 갖는다. 일변수 다항식과 달리, 다변수 다항식의 나머지 있는 나눗셈은 단항식들 사이의 적절한 순서 관계의 선택에 의존한다. 다변수 다항식의 나머지 있는 나눗셈은 다변수 다항식환 위의 유한 생성 자유 가군에까지 일반화된다.

## (정수) 나눗셈 정리
### 정의
두 정수 m,n이 주어졌고, n\ne 0이라고 하자. **나눗셈 정리**에 따르면, 다음 두 조건을 만족시키는 정수 q,r가 유일하게 존재한다.
* m=nq+r
* 0\le r
여기서 |\cdot|는 절댓값이다. 이 경우 q,r를 각각 m을 n으로 나눈 **[[몫]]**과 **[[나머지]]**라고 하며, 두 정수 m,n으로부터 몫 q와 나머지 r를 얻는 연산을 **나머지 있는 나눗셈**이라고 한다. 추상대수학의 관점에서, 나눗셈 정리는 정수환 \mathbb Z이 유클리드 정역임을 나타낸다.

우선 q,r가 존재한다는 사실을 보이자. 우선 m\ge 0인 경우를 생각하자. 정수 n\ne 0을 고정하고 m에 대한 수학적 귀납법을 사용하자. 만약 m이라면, q=0 및 r=m은 원하는 조건을 만족시킨다. 이제, m\ge|n|이라고 하고, m보다 작은 모든 정수는 n으로 나눈 몫과 나머지를 갖는다고 가정하자. 그렇다면 m-1이므로 수학적 귀납법의 가정에 의하여 다음 두 조건을 만족시키는 정수 q_1,r_1이 존재한다.
* m-1=nq_1+r_1
* 0\le r_1
만약 r_1\ne|n|-1일 경우, q=q_1과 r=r_1+1은 원하는 조건을 만족시킨다. 만약 r_1=|n|-1일 경우 q=q_1+|n|/n과 r=0을 취하면 된다. 수학적 귀납법에 의하여, 임의의 m\ge 0에 대하여, 정리 속 조건을 만족시키는 q,r가 존재한다. n을 미리 고정하였으므로 이는 임의의 m\ge 0 및 n\ne 0에 적용된다.

이제 m인 경우를 생각하자. 이 경우 -m>0은 양의 정수이므로, 다음 두 조건을 만족시키는 정수 q_1,r_1이 존재한다.
* -m=nq_1+r_1
* 0\le r_1
만약 r_1\ne 0이라면 q=-q_1-|n|/n과 r=|n|-r_1을 취하고, 만약 r_1=0이라면 q=-q_1과 r=0을 취하자. 그렇다면 q,r는 원하는 조건을 만족시킨다. 이에 따라 q,r는 임의의 정수 m 및 0이 아닌 정수 n에 대하여 존재한다.

이제 q,r가 유일하다는 사실을 보이자. 정수 q_1,r_1,q_2,r_2가 다음 조건을 만족시킨다고 가정하자.
* m=nq_1+r_1=nq_2+r_2
* 0\le r_1
* 0\le r_2
그렇다면,
:n(q_1-q_2)=r_2-r_1
이며, 양변을 n으로 나누고 절댓값을 취하면
:|q_1-q_2|=\frac
을 얻는다. 즉, q_1=q_2이며, 따라서 r_1=r_2이다. 이에 따라, 정리 속 조건을 만족시키는 q,r는 유일하다.

### 예
a=7을 b=3으로 나눈 몫은 q=2, 나머지는 r=1이다 (7=3\times 2+1).

### 따름정리
#### 대분수 전개
모든 유리수는 정수와 분모가 양의 정수인 기약 진분수의 합으로 유일하게 나타낼 수 있다. 즉, 유리수 a/b (a,b는 정수, b>0, a와 b는 서로소)에 대하여, a를 b로 나눈 몫과 나머지를 각각 q,r라고 하면,
:\frac ab=q+\frac rb
이며, 이 경우 r/b는 기약 분수이자 진분수이다.

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

우선 q(x),r(x)가 존재함을 증명하자. 임의의 g(x)\ne 0을 고정하고 \deg f에 대한 수학적 귀납법을 사용하자. 만약 \deg f라면, q(x)=0과 r(x)=f(x)를 취하면 된다. 이제, \deg f\ge\deg g라고 하고, 차수가 f(x)보다 낮은 다항식이 항상 g(x)로 나눈 몫과 나머지를 갖는다고 가정하자. 차수 \deg f에 대한 수학적 귀납법을 사용하자.
:f(x)=ax^{\deg f}+\cdots
:g(x)=bx^{\deg g}+\cdots
라고 하고,
:f_1(x)=f(x)-g(x)b^{-1}ax^{\deg f-\deg g}
라고 하자. 그렇다면 \deg f_1이므로, 수학적 귀납법의 가정에 의하여 다음 두 조건을 만족시키는 q_1,r\in R[x]가 존재한다.
* f_1(x)=g(x)q_1(x)+r(x)
* \deg r
그렇다면
:q(x)=q_1(x)+b^{-1}ax^{\deg f-\deg g}
와 r(x)는 원하는 조건을 만족시킨다.

이제 q(x),r(x)가 유일함을 증명하자. q_1,r_1,q_2,r_2\in R[x]가 다음 조건을 만족시킨다고 가정하자.
* f(x)=g(x)q_1(x)+r_1(x)=g(x)q_2(x)+r_2(x)
* \deg r_1
* \deg r_2
그렇다면
:r_1(x)-r_2(x)=g(x)(q_2(x)-q_1(x))
이며, 또한 g(x)의 최고차항의 계수는 왼쪽 또는 오른쪽 영인자가 아니므로,
:\deg g+\deg(q_2-q_1)=\deg(g(q_2-q_1))=\deg(r_2-r_1)\le\max\{\deg r_1,\deg r_2\}
이다. 따라서 q_1(x)=q_2(x), r_1(x)=r_2(x)이다.

보다 일반적으로, 환 R에서 계수를 취하는 다항식 f,g\in R[x]가 주어졌고, g(x)\ne 0이며, g(x)의 최고차항의 계수를 b라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 q,r\in R[x]가 존재한다.
* b^{\max\{\deg f-\deg g+1,0\}}f(x)=g(x)q(x)+r(x)
* \deg r
마찬가지로, 다음 두 조건을 만족시키는 다항식 \tilde q,\tilde r\in R[x]가 존재한다.
* f(x)b^{\max\{\deg f-\deg g+1,0\}}=\tilde q(x)g(x)+\tilde r(x)
* \deg\tilde r
만약 b\in R가 가역원이라면, 이러한 q(x),r(x),\tilde q(x),\tilde r(x)는 유일하다.

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

체 K에서 계수를 취하는 다항식 f,g\in K[x]가 주어졌고, g(x)\ne 0이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 q,r\in K[x]가 유일하게 존재한다.
* f(x)=g(x)q(x)+r(x)
* \deg r
이에 따라, 체에 대한 일변수 다항식환 K[x]는 유클리드 정역을 이룬다.

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

### 예
정수 계수 다항식 f(x)=x^2-x-1를 g(x)=x+1로 나눈 몫과 나머지는 각각 q(x)=x-2와 r(x)=1이다.

임의의 환 R에서, 다항식 ax를 bx (b는 가역원)로 나눈 몫은 b^{-1}a, 나머지는 0이다. 그 반대환 R^{\operatorname{op}}에서 몫과 나머지는 각각 ab^{-1}와 0이다. R가 가환환일 경우 반대환은 자기 자신과 일치하므로, R와 R^{\operatorname{op}}에서의 몫과 나머지는 일치한다.

### 따름정리
#### 나머지 정리

환 R에서 계수를 취하는 다항식 f\in R[x]가 주어졌고, R를 부분환으로 갖는 환 S의 원소 a\in S가 R의 모든 원소와 가환한다고 하자 (임의의 b\in R에 대하여, ab=ba). **나머지 정리**(-定理, )에 따르면, f(x)를 x-a로 나눈 나머지는 f(a)이다.

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

다항식 나눗셈 정리에 따라 다음 두 조건을 만족시키는 q,r\in S[x]가 존재한다.
* f(x)=(x-a)q(x)+r(x)
* \deg r
따라서 r\in S이다. 함수
:R[x]\to S
:g(x)\mapsto g(a)
는 자명하게 덧셈을 보존한다. 또한, a가 R의 모든 원소와 가환하므로 이는 곱셈을 보존한다. 즉, 환 준동형이다. 이를
:f(x)=(x-a)q(x)+r(x)
에 적용하면
:f(a)=(a-a)q(a)+r(a)=r
을 얻는다.

#### 인수 정리

환 R에서 계수를 취하는 다항식 f\in R[x]가 주어졌고, R를 부분환으로 갖는 환 S의 원소 a\in S가 R의 모든 원소와 가환한다고 하자 (임의의 b\in R에 대하여, ab=ba). **인수 정리**(因數定理, )에 따르면, 다음 두 조건이 서로 동치이다.
* x-a\mid f(x)
* f(a)=0
특히, 만약 S가 가환환일 경우 이는 임의의 a\in S에 대하여 성립한다.

만약 x-a\mid f(x)라면, f(x)=(x-a)q(x)인 q\in S[x]가 존재하므로,
:f(a)=(a-a)q(a)=0
이다.

만약 f(a)=0이라면, 나머지 정리에 따라
:f(x)=(x-a)q(x)+f(a)=(x-a)q(x)
인 q\in S[x]가 존재하므로 x-a\mid f(x)이다.

#### 대분수 전개
체 K에서 계수를 취하는 유리 함수는 다음과 같은 꼴로 유일하게 나타낼 수 있다.
:q(x)+\frac{r(x)}{g(x)}\in K(x)
여기서 다항식 q,r,g\in K[x]는 다음 조건을 만족시킨다.
* \deg r
* g(x)는 일계수 다항식이다.
* \gcd\{r,g\}=1

#### g진 전개
환 R에서 계수를 취하는 두 다항식 f,g\in R[x]가 주어졌고, \deg f\ge 0, \deg g\ge 1이며, g(x)의 최고차항의 계수가 R의 가역원이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 q_0,\dots q_{\lfloor\deg f/{\deg g}\rfloor}\in R[x]가 유일하게 존재한다.
* f(x)=q_0(x)+g(x)q_1(x)+\cdots+g(x)^{\lfloor\deg f/{\deg g}\rfloor}q_{\lfloor\deg f/{\deg g}\rfloor}(x)
* \deg q_i
마찬가지로, 다음 두 조건을 만족시키는 다항식 \tilde q_0,\dots,\tilde q_{\lfloor\deg f/{\deg g}\rfloor}\in R[x]가 유일하게 존재한다.
* f(x)=\tilde q_0(x)+\tilde q_1(x)g(x)+\cdots+\tilde q_{\lfloor\deg f/{\deg g}\rfloor}(x)g(x)^{\lfloor\deg f/{\deg g}\rfloor}
* \deg\tilde q_i
여기서 \lfloor\cdot\rfloor는 바닥 함수이다. 특히, g(x)=x일 경우 이는 다항식 f(x)의 통상적인 전개와 같다.

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

## 유클리드 정역

### 정의
정수환 \mathbb Z 또는 체 K 위의 다항식환 K[x]와 같이, 나머지 있는 나눗셈을 할 수 있고 정역을 이루는 환을 유클리드 정역이라고 한다. 구체적으로, 유클리드 정역은 다음을 만족시키는 함수 \operatorname N\colon R\setminus\{0\}\to\mathbb N가 존재하는 정역 R이다.
* 임의의 a,b\in R (b\ne 0)에 대하여, a=bq+r이며, r=0이거나 \operatorname N(r)인 q,r\in R이 존재한다.
이 경우 q,r는 정수환이나 다항식환에서와 달리 유일하지 않을 수 있다.

### 예
정수환 \mathbb Z은 절댓값 함수 n\mapsto|n|에 대하여 유클리드 정역을 이룬다. 체 K 위의 다항식환 K[x]는 차수 함수 f\mapsto \deg f에 대하여 유클리드 정역을 이룬다.

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

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

#### 가우스 정수환
허수 이차 수체 \mathbb Q(i)의 대수적 정수환
:\mathbb Z[i]=\{a+bi\colon a,b\in\mathbb Z\}
를 가우스 정수환이라고 한다. \mathbb Q(i) 위의 체 노름은
:\operatorname N(a+bi)=a^2+b^2\qquad(a,b\in\mathbb Z)
이며, 가우스 정수환은 체 노름에 대하여 유클리드 정역을 이룬다.

임의의 a+bi,c+di\in\mathbb Z[i] (a,b,c,d\in\mathbb Z, c+di\ne 0)에 대하여,
:\frac{a+bi}{c+di}=e+fi
:e,f\in\mathbb Q
라고 하자. 이제,
:|e-p|\le\frac 12
:|f-q|\le\frac 12
인 p,q\in\mathbb Z를 취하고
:r+si=(c+di)((e-p)+(f-q)i)=(a+bi)-(c+di)(p+qi)\in\mathbb Z[i]
라고 하자. 그렇다면,
:a+bi=(c+di)(p+qi)+(r+si)
:\operatorname N(r+si)=\operatorname N(c+di)\operatorname N((e-p)+(f-q)i)\le\frac 12\operatorname N(c+di)
이다. 이에 따라 \mathbb Z[i]는 체 노름 \operatorname N에 대하여 유클리드 정역을 이룬다.

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

#### −3에 대한 이차 수체의 대수적 정수환
허수 이차 수체 \mathbb Q(\sqrt{-3})의 대수적 정수환
:\mathbb Z[\sqrt{-3}]=\left\{\frac{a+b\sqrt{-3}}2\colon a,b\in\mathbb Z,\;a\equiv b\pmod 2\right\}
은 체 노름
:\operatorname N(a+b\sqrt{-3})=a^2+3b^2\qquad(a,b\in\mathbb Q)
에 대하여 유클리드 정역을 이룬다.

임의의 a+b\sqrt{-3},c+d\sqrt{-3}\in\mathbb Z[\sqrt{-3}] (a,b,c,d\in\mathbb Q, c+d\sqrt{-3}\ne 0)에 대하여,
:\frac{a+b\sqrt{-3}}{c+d\sqrt{-3}}=e+f\sqrt{-3}
:e,f\in\mathbb Q
라고 하자. 이제,
:|2e-p|\le 1
:|2f-q|\le\frac 12
:p\equiv q\pmod 2
인 p,q\in\mathbb Z를 취하고,
:r+s\sqrt{-3}=(c+d\sqrt{-3})\left(\frac{2e-p}2+\frac{2f-q}2\sqrt{-3}\right)=(a+bi)-(c+d\sqrt{-3})\left(\frac p2+\frac q2\sqrt{-3}\right)\in\mathbb Z[\sqrt{-3}]
이라고 하자. 그렇다면,
:a+b\sqrt{-3}=(c+d\sqrt{-3})\left(\frac p2+\frac q2\sqrt{-3}\right)+(r+s\sqrt{-3})
:\operatorname N(r+s\sqrt{-3})=\operatorname N(c+d\sqrt{-3})\operatorname N\left(\frac{2e-p}2+\frac{2f-q}2\sqrt{-3}\right)\le\frac 7{16}\operatorname N(c+d\sqrt{-3})
이다. 이에 따라 \mathbb Z[\sqrt{-3}]은 체 노름 \operatorname N에 대하여 유클리드 정역을 이룬다.

## 다변수 다항식

### 정의
#### 단항식 순서

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

체 K에서 계수를 취하는 다변수 다항식환 K[x_1,\dots,x_n] 위의 **[[단항식 순서]]**(單項式順序, )는 다음 세 조건을 만족시키는, 단항식의 집합 위의 전순서 \le이다.
* 만약 x_1^{i_1}\cdots x_n^{i_n}이라면, (x_1^{i_1}\cdots x_n^{i_n})(x_1^{k_1}\cdots x_n^{k_n})이다.
* 항상 1\le x_1^{i_1}\cdots x_n^{i_n}이다.
* \le는 정렬 전순서이다.
두 번째와 세 번째 조건은 하나만 취하여도 좋다. 첫 번째와 두 번째 조건은 세 번째 조건을 함의하며, 반대로 첫 번째와 세 번째 조건도 두 번째 조건을 함의하기 때문이다. 정의에 따라, 만약 x_1^{i_1}\cdots x_n^{i_n}\mid x_1^{j_1}\cdots x_n^{j_n}이라면, x_1^{i_1}\cdots x_n^{i_n}\le x_1^{j_1}\cdots x_n^{j_n}이다.

체 K에서 계수를 취하는 다변수 다항식환 K[x_1,\dots,x_n] 위의 단항식 순서 \le가 주어졌다고 하자. 그렇다면, 임의의 다변수 다항식 f\in K[x_1,\dots,x_n]은 그 (0이 아닌) 항들을 \le에 대하여 큰 항부터 작은 항까지의 순서대로 정렬하여
:f(x_1,\dots,x_n)=a_{m_1,\dots,m_n}x_1^{m_1}\cdots x_n^{m_n}+\cdots
꼴로 나타낼 수 있다. 이 경우, 단항식 순서 \le에 대한 f의 **최고차항**(最高次項, )과 **최고차 계수**(最高次係數, )와 **최고차 단항식**(最高次單項式, )은 각각 다음과 같다.
:\operatorname{lt}f=a_{m_1,\dots,m_n}x_1^{m_1}\cdots x_n^{m_n}
:\operatorname{lc}f=a_{m_1,\dots,m_n}
:\operatorname{lm}f=x_1^{m_1}\cdots x_n^{m_n}
(다항식 0의 최고차항, 최고차 계수, 최고차 단항식은 보통 모두 0으로 정의하며, 항상 \operatorname{lm}0\le\operatorname{lm}f이라고 생각한다.)

#### 다변수 나눗셈

체 K에서 계수를 취하는 다변수 다항식 f,g_1,\dots,g_k\in K[x_1,\dots,x_n] 및 단항식 순서 \le가 주어졌고, g_1,\dots,g_k\ne 0이라고 하자. 그렇다면, 다음을 만족시키는 다변수 다항식 q_1,\dots,q_k,r\in K[x_1,\dots,x_n]이 존재한다.
* f=g_1q_1+\cdots+g_kq_k+r
* \operatorname{lm}g_iq_i\le\operatorname{lm}f\qquad(1\le i\le k)
* \operatorname{lm}r\le\operatorname{lm}f
* r에 등장하는 모든 (0이 아닌 계수의) 단항식은 \operatorname{lm}g_1,\dots,\operatorname{lm}g_k의 배수가 아니다.
이 경우 몫과 나머지 q_1,\dots,q_k,r는 유일할 필요가 없다. 만약 \{g_1,\dots,g_k\}가 (g_1,\dots,g_k)의 그뢰브너 기저를 이룰 경우, 나머지 r는 항상 유일하며, 임의의 f\in K[x_1,\dots,x_n]에 대하여, 다음 두 조건이 서로 동치이다.
* f\in(g_1,\dots,g_k)
* f를 g_1,\dots,g_k로 나눈 나머지는 0이다.

#### 그뢰브너 기저

체 K에서 계수를 취하는 다변수 다항식환 K[x_1,\dots,x_n]의 아이디얼 \mathfrak a\subseteq K[x_1,\dots,x_n] 및 단항식 순서 \le가 주어졌다고 하자. 유한 집합 \{g_1,\dots,g_k\}\subseteq\mathfrak a\setminus\{0\}에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 \{g_1,\dots,g_k\}를 \mathfrak a의 **[[그뢰브너 기저]]**라고 한다.
* (\operatorname{lm}\mathfrak a)=(\operatorname{lm}g_1,\dots,\operatorname{lm}g_k)
* 임의의 f\in\mathfrak a에 대하여, \operatorname{lm}g_i\mid\operatorname{lm}f인 1\le i\le k가 존재한다.
* 임의의 f\in\mathfrak a에 대하여, f를 g_1,\dots,g_k로 나눈 모든 나머지는 0이다.
* 임의의 f\in\mathfrak a에 대하여, f를 g_1,\dots,g_k로 나눈 나머지 가운데 적어도 하나는 0이다.
* (부흐베르거 알고리즘) \mathfrak a=(g_1,\dots,g_k)이며, 임의의 1\le i에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j)를 g_1,\dots,g_k로 나눈 모든 나머지는 0이다.
* (부흐베르거 알고리즘) \mathfrak a=(g_1,\dots,g_k)이며, 임의의 1\le i에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j)를 g_1,\dots,g_k로 나눈 나머지 가운데 적어도 하나는 0이다.
여기서, 임의의 다항식 집합 S\subseteq K[x_1,\dots,x_n]에 대하여, (S)는 S로 생성된 K[x_1,\dots,x_n]의 아이디얼이다. S=\{s_1,\dots,s_\}가 유한 집합일 경우 (S)는 (s_1,\dots,s_)로 표기할 수 있다. 또한,
:\operatorname{lm}S=\{\operatorname{lm}s\colon s\in S\}
이다. \operatorname{lcm}은 최소 공배수를 뜻한다.

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

#### 부흐베르거 알고리즘

체 K에서 계수를 취하는 유한 개의 다변수 다항식 \{g_1,\dots,g_k\}\subseteq K[x_1,\dots,x_n]\setminus\{0\}으로 생성된 아이디얼 (g_1,\dots,g_k)의 그뢰브너 기저는 다음과 같은 과정을 통해 찾을 수 있으며, 이를 **[[부흐베르거 알고리즘]]**()이라고 한다.
# G=\{g_1,\dots,g_k\}에서 시작한다.
# 각 1\le i에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j)를 g_1,\dots,g_로 나눈 나머지 r_{ij}를 구하되, 0이 아닌 나머지 r_{ij}\ne 0을 발견했거나, 모든 1\le i에 대하여 구했다면 멈춘다.
# 만약 0이 아닌 나머지 r_{i_0j_0}\ne 0을 발견했다면, g_{|G|+1}=r_{i_0j_0}을 G의 새로운 원소로 추가하여 2번째 단계를 반복한다. 만약 임의의 1\le i에 대하여 r_{ij}=0이라면, G는 (g_1,\dots,g_k)의 그뢰브너 기저이다.

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

## 외부 링크
* 

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