나눗셈 정리

수학에서 나눗셈 정리(-定理, 영어: division theorem)는 임의의 정수를 0이 아닌 정수로 나눈 몫과 나머지를 유일하게 정의할 수 있다는 정리이다. 두 정수로부터 몫과 나머지를 얻는 연산을 나머지 있는 나눗셈(영어: division with remainders) 또는 유클리드 나눗셈(영어: Euclidean division)이라고 한다. 양의 정수를 양의 정수로 나눈 몫은 나뉘는 수가 음의 정수가 되기 직전까지 나누는 수를 뺀 횟수를 나타내며, 나머지는 이 횟수만큼 뺀 차를 나타낸다. 예를 들어, 17에서 5를 3번 빼면 2가 남으며, 3번 이상 빼면 음의 정수가 되므로, 17를 5로 나눈 몫은 3이며 나머지는 2이다. 이를 곱셈을 사용하여 표기하면 다음과 같다.

$17=5\times 3+2$. 17개를 한 줄에 5개씩 나열하면 3줄에 2개가 남는다.

$9=4\times 2+1$. 9조각의 파이를 4명의 사람이 2조각씩 나눠 먹으면 1조각이 남는다.

$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\neq 0$이라고 하자. 나눗셈 정리에 따르면, 다음 두 조건을 만족시키는 정수 $q,r$가 유일하게 존재한다.

• $m=nq+r$
• $0\leq r<|n|$

여기서 $|\cdot |$는 절댓값이다. 이 경우 $q,r$를 각각 $m$을 $n$으로 나눈 몫과 나머지라고 하며, 두 정수 $m,n$으로부터 몫 $q$와 나머지 $r$를 얻는 연산을 나머지 있는 나눗셈이라고 한다. 추상대수학의 관점에서, 나눗셈 정리는 정수환 $\mathbb {Z}$이 유클리드 정역임을 나타낸다.

증명:

우선 $q,r$가 존재한다는 사실을 보이자. 우선 $m\geq 0$인 경우를 생각하자. 정수 $n\neq 0$을 고정하고 $m$에 대한 수학적 귀납법을 사용하자. 만약 $m<|n|$이라면, $q=0$ 및 $r=m$은 원하는 조건을 만족시킨다. 이제, $m\geq |n|$이라고 하고, $m$보다 작은 모든 정수는 $n$으로 나눈 몫과 나머지를 갖는다고 가정하자. 그렇다면 $m-1<m$이므로 수학적 귀납법의 가정에 의하여 다음 두 조건을 만족시키는 정수 $q_{1},r_{1}$이 존재한다.

• $m-1=nq_{1}+r_{1}$
• $0\leq r_{1}<|n|$

만약 $r_{1}\neq |n|-1$일 경우, $q=q_{1}$과 $r=r_{1}+1$은 원하는 조건을 만족시킨다. 만약 $r_{1}=|n|-1$일 경우 $q=q_{1}+|n|/n$과 $r=0$을 취하면 된다. 수학적 귀납법에 의하여, 임의의 $m\geq 0$에 대하여, 정리 속 조건을 만족시키는 $q,r$가 존재한다. $n$을 미리 고정하였으므로 이는 임의의 $m\geq 0$ 및 $n\neq 0$에 적용된다.

이제 $m<0$인 경우를 생각하자. 이 경우 $-m>0$은 양의 정수이므로, 다음 두 조건을 만족시키는 정수 $q_{1},r_{1}$이 존재한다.

• $-m=nq_{1}+r_{1}$
• $0\leq r_{1}<|n|$

만약 $r_{1}\neq 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\leq r_{1}<|n|$
• $0\leq r_{2}<|n|$

그렇다면,

$n(q_{1}-q_{2})=r_{2}-r_{1}$

이며, 양변을 $n$으로 나누고 절댓값을 취하면

$|q_{1}-q_{2}|={\frac {|r_{2}-r_{1}|}{|n|}}<{\frac {|n|-0}{|n|}}=1$

을 얻는다. 즉, $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 {a}{b}}=q+{\frac {r}{b}}$

이며, 이 경우 $r/b$는 기약 분수이자 진분수이다.

다항식 나눗셈 정리

정의

환 $R$에서 계수를 취하는 두 다항식 $f,g\in R[x]$가 주어졌고, $g(x)\neq 0$이며, $g(x)$의 최고차항의 계수가 $R$의 가역원이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 $q,r\in R[x]$가 유일하게 존재한다.^{:121, §III.5, Proposition 5.5:173-174, §IV.1, Theorem 1.1}

• $f(x)=g(x)q(x)+r(x)$
• $\deg r<\deg g$

마찬가지로, 다음 두 조건을 만족시키는 다항식 ${\tilde {q}},{\tilde {r}}\in R[x]$가 유일하게 존재한다.

• $f(x)={\tilde {q}}(x)g(x)+{\tilde {r}}(x)$
• $\deg {\tilde {r}}<\deg g$

여기서 $\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)\neq 0$에 대하여 성립한다.

증명:

우선 $q(x),r(x)$가 존재함을 증명하자. 임의의 $g(x)\neq 0$을 고정하고 $\deg f$에 대한 수학적 귀납법을 사용하자. 만약 $\deg f<\deg g$라면, $q(x)=0$과 $r(x)=f(x)$를 취하면 된다. 이제, $\deg f\geq \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}<\deg f$이므로, 수학적 귀납법의 가정에 의하여 다음 두 조건을 만족시키는 $q_{1},r\in R[x]$가 존재한다.

• $f_{1}(x)=g(x)q_{1}(x)+r(x)$
• $\deg r<\deg g$

그렇다면

$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 g$
• $\deg r_{2}<\deg g$

그렇다면

$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})\leq \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)\neq 0$이며, $g(x)$의 최고차항의 계수를 $b$라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 $q,r\in R[x]$가 존재한다.^{:IV.10, §IV.6, Proposition 10}

• $b^{\max\{\deg f-\deg g+1,0\}}f(x)=g(x)q(x)+r(x)$
• $\deg r<\deg g$

마찬가지로, 다음 두 조건을 만족시키는 다항식 ${\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}}<\deg g$

만약 $b\in R$가 가역원이라면, 이러한 $q(x),r(x),{\tilde {q}}(x),{\tilde {r}}(x)$는 유일하다.

체의 경우

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

체 $K$에서 계수를 취하는 다항식 $f,g\in K[x]$가 주어졌고, $g(x)\neq 0$이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 $q,r\in K[x]$가 유일하게 존재한다.

• $f(x)=g(x)q(x)+r(x)$
• $\deg r<\deg g$

이에 따라, 체에 대한 일변수 다항식환 $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$). 나머지 정리(-定理, 영어: remainder theorem)에 따르면, $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<\deg(x-a)=1$

따라서 $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$). 인수 정리(因數定理, 영어: factor theorem)에 따르면, 다음 두 조건이 서로 동치이다.^{:122, §III.5, Proposition 5.7:175, §IV.1, Theorem 1.4}

• $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<\deg g$
• $g(x)$는 일계수 다항식이다.
• $\gcd\{r,g\}=1$

g진 전개

환 $R$에서 계수를 취하는 두 다항식 $f,g\in R[x]$가 주어졌고, $\deg f\geq 0$, $\deg g\geq 1$이며, $g(x)$의 최고차항의 계수가 $R$의 가역원이라고 하자. 그렇다면, 다음 두 조건을 만족시키는 다항식 $q_{0},\dots q_{\lfloor \deg f/{\deg g}\rfloor }\in R[x]$가 유일하게 존재한다.^{:124, §III.5, Exercise 3:189, §IV.5, Theorem 5.3}

• $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}<\deg g\qquad (0\leq i\leq \lfloor \deg f/{\deg g}\rfloor )$

마찬가지로, 다음 두 조건을 만족시키는 다항식 ${\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}<\deg g\qquad (0\leq i\leq \lfloor \deg f/{\deg g}\rfloor )$

여기서 $\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\neq 0$)에 대하여, $a=bq+r$이며, $r=0$이거나 $\operatorname {N} (r)<\operatorname {N} (b)$인 $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\neq 0$)에 대하여,

${\frac {a+bi}{c+di}}=e+fi$

$e,f\in \mathbb {Q}$

라고 하자. 이제,

$|e-p|\leq {\frac {1}{2}}$

$|f-q|\leq {\frac {1}{2}}$

인 $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)\leq {\frac {1}{2}}\operatorname {N} (c+di)<\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}}\neq 0$)에 대하여,

${\frac {a+b{\sqrt {-3}}}{c+d{\sqrt {-3}}}}=e+f{\sqrt {-3}}$

$e,f\in \mathbb {Q}$

라고 하자. 이제,

$|2e-p|\leq 1$

$|2f-q|\leq {\frac {1}{2}}$

$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 {p}{2}}+{\frac {q}{2}}{\sqrt {-3}}\right)\in \mathbb {Z} [{\sqrt {-3}}]$

이라고 하자. 그렇다면,

$a+b{\sqrt {-3}}=(c+d{\sqrt {-3}})\left({\frac {p}{2}}+{\frac {q}{2}}{\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)\leq {\frac {7}{16}}\operatorname {N} (c+d{\sqrt {-3}})<\operatorname {N} (c+d{\sqrt {-3}})$

이다. 이에 따라 $\mathbb {Z} [{\sqrt {-3}}]$은 체 노름 $\operatorname {N}$에 대하여 유클리드 정역을 이룬다.

다변수 다항식

 이 부분의 본문은 그뢰브너 기저입니다.

정의

단항식 순서

 이 부분의 본문은 단항식 순서입니다.

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

체 $K$에서 계수를 취하는 다변수 다항식환 $K[x_{1},\dots ,x_{n}]$ 위의 단항식 순서(單項式順序, 영어: monomial order)는 다음 세 조건을 만족시키는, 단항식의 집합 위의 전순서 $\leq$이다.

• 만약 $x_{1}^{i_{1}}\cdots x_{n}^{i_{n}}<x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}$이라면, $(x_{1}^{i_{1}}\cdots x_{n}^{i_{n}})(x_{1}^{k_{1}}\cdots x_{n}^{k_{n}})<(x_{1}^{j_{1}}\cdots x_{n}^{j_{n}})(x_{1}^{k_{1}}\cdots x_{n}^{k_{n}})$이다.
• 항상 $1\leq x_{1}^{i_{1}}\cdots x_{n}^{i_{n}}$이다.
• $\leq$는 정렬 전순서이다.

두 번째와 세 번째 조건은 하나만 취하여도 좋다. 첫 번째와 두 번째 조건은 세 번째 조건을 함의하며, 반대로 첫 번째와 세 번째 조건도 두 번째 조건을 함의하기 때문이다. 정의에 따라, 만약 $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}}\leq x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}$이다.

체 $K$에서 계수를 취하는 다변수 다항식환 $K[x_{1},\dots ,x_{n}]$ 위의 단항식 순서 $\leq$가 주어졌다고 하자. 그렇다면, 임의의 다변수 다항식 $f\in K[x_{1},\dots ,x_{n}]$은 그 (0이 아닌) 항들을 $\leq$에 대하여 큰 항부터 작은 항까지의 순서대로 정렬하여

$f(x_{1},\dots ,x_{n})=a_{m_{1},\dots ,m_{n}}x_{1}^{m_{1}}\cdots x_{n}^{m_{n}}+\cdots$

꼴로 나타낼 수 있다. 이 경우, 단항식 순서 $\leq$에 대한 $f$의 최고차항(最高次項, 영어: leading term)과 최고차 계수(最高次係數, 영어: leading coefficient)와 최고차 단항식(最高次單項式, 영어: leading monomial)은 각각 다음과 같다.

$\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\leq \operatorname {lm} f$이라고 생각한다.)

다변수 나눗셈

 이 부분의 본문은 다변수 나눗셈입니다.

체 $K$에서 계수를 취하는 다변수 다항식 $f,g_{1},\dots ,g_{k}\in K[x_{1},\dots ,x_{n}]$ 및 단항식 순서 $\leq$가 주어졌고, $g_{1},\dots ,g_{k}\neq 0$이라고 하자. 그렇다면, 다음을 만족시키는 다변수 다항식 $q_{1},\dots ,q_{k},r\in K[x_{1},\dots ,x_{n}]$이 존재한다.

• $f=g_{1}q_{1}+\cdots +g_{k}q_{k}+r$
• $\operatorname {lm} g_{i}q_{i}\leq \operatorname {lm} f\qquad (1\leq i\leq k)$
• $\operatorname {lm} r\leq \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}]$ 및 단항식 순서 $\leq$가 주어졌다고 하자. 유한 집합 $\{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\leq i\leq 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\leq i<j\leq k$에 대하여, $\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\leq i<j\leq k$에 대하여, $\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)$는 $(s_{1},\dots ,s_{|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})$의 그뢰브너 기저는 다음과 같은 과정을 통해 찾을 수 있으며, 이를 부흐베르거 알고리즘(영어: Buchberger’s algorithm)이라고 한다.

1. $G=\{g_{1},\dots ,g_{k}\}$에서 시작한다.
2. 각 $1\leq i<j\leq |G|$에 대하여, $\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_{|G|}$로 나눈 나머지 $r_{ij}$를 구하되, 0이 아닌 나머지 $r_{ij}\neq 0$을 발견했거나, 모든 $1\leq i<j\leq |G|$에 대하여 구했다면 멈춘다.
3. 만약 0이 아닌 나머지 $r_{i_{0}j_{0}}\neq 0$을 발견했다면, $g_{|G|+1}=r_{i_{0}j_{0}}$을 $G$의 새로운 원소로 추가하여 2번째 단계를 반복한다. 만약 임의의 $1\leq i<j\leq |G|$에 대하여 $r_{ij}=0$이라면, $G$는 $(g_{1},\dots ,g_{k})$의 그뢰브너 기저이다.

같이 보기

• 유클리드의 보조 정리
• 유클리드 호제법

외부 링크

• “Division theorem”. 《ProofWiki》 (영어).