베주 항등식: 정수와 체 위의 다항식

이 글의 목차

인터랙티브

베주 계수는 나머지와 함께 이동한다

확장자동초기화

a = 30, b = 18에 대한 확장 유클리드 표

q	r	x	y	a·x + b·y

확장을 눌러 다음 나머지와 계수를 계산하세요.

a·x + b·y = gcd(a, b)

최대공약수는 두 수를 나누는 수일 뿐 아니라, 두 수의 정수 선형결합으로도 나타난다. 이 성질은 예를 들어 모듈러 역원을 구할 때 쓰인다. $a=30$, $b=18$이면 유클리드 알고리즘에서 $30-18=12$, $18-12=6$, $12-2\cdot6=0$이므로

$6=18-12=2\cdot18-30.$

베주 항등식은 입력이 음수인 경우까지 포함해 이러한 계수가 항상 존재함을 말한다.

정수에 대한 베주 항등식

$a,b\in\mathbb Z$가 동시에 0은 아니라고 하고 $g=\gcd(|a|,|b|)>0$라 하자. 그러면 어떤 정수 $x,y$에 대해

$ax+by=g$

가 성립한다. 더 나아가 정수 선형결합 전체는 정확히 $g$의 배수 전체다.

$\{ax+by:x,y\in\mathbb Z\}=g\mathbb Z.$

최소 양의 선형결합을 이용한 증명

다음 집합을 생각하자.

$S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.$

$a,b$ 중 적어도 하나는 0이 아니므로 $S$는 공집합이 아니다. 0이 아닌 입력의 절댓값은 계수를 $1$ 또는 $-1$로 적절히 고르고 다른 계수를 0으로 두어 얻을 수 있는 양의 결합이다. 정렬성 원리에 따라 $S$에는 최소 원소 $m=ax_0+by_0>0$가 있다.

$a$를 $m$으로 나누면 $a=qm+r$, $0\le r<m$이다. $m=ax_0+by_0$이므로

$r=a-qm=a(1-qx_0)+b(-qy_0)$

이고, $r$도 정수 선형결합이다. $r>0$이면 $S$에 속하면서 $m$보다 작아 최소성에 모순이므로 $r=0$이다. 따라서 $m\mid a$다. 같은 논리를 $b$에 적용하면 $m\mid b$도 얻는다.

$a,b$의 모든 공약수는 모든 선형결합, 특히 $m$을 나눈다. 그러므로 $m$은 양의 공약수이면서 모든 공약수의 배수인 최대공약수, 즉 $g$다. 정의한 표현에서 $ax_0+by_0=g$를 얻는다.

$g$가 두 입력을 나누므로 모든 $ax+by$를 나눈다. 반대로 $ax_0+by_0=g$에 임의의 정수 $n$을 곱하면 $ng=a(nx_0)+b(ny_0)$이다. 따라서 선형결합은 정확히 $g\mathbb Z$다.

다항식 버전—체 위에서

이는 계수의 범위가 다른 별도의 명제다. 체 $K$와 동시에 0은 아닌 $f,g\in K[x]$를 생각하자. $d$를 최고차항 계수가 1인 최대공약다항식, $I=(f,g)\subseteq K[x]$를 $f,g$가 생성하는 아이디얼이라 하면

$$\begin{aligned} uf+vg &= d\quad(u,v\in K[x]),\\ I=dK[x]. \end{aligned}$$

가 성립한다.

$I=\{uf+vg:u,v\in K[x]\}$의 0이 아닌 원소 중 차수가 가장 작은 것을 골라 최고차항 계수를 1로 맞추고 이를 $d$라 하자. 체 위에서 다항식 나눗셈을 하면 $f=qd+r$이며, $r=0$이거나 $\deg r<\deg d$다. $d\in I$이므로 $r=f-qd\in I$이고, 최소 차수성에 따라 $r=0$이다. 따라서 $d\mid f$이며 같은 방법으로 $d\mid g$다. $f,g$의 공약다항식은 $I$의 모든 원소, 특히 $d$를 나누므로 $d$는 최고차항 계수가 1인 최대공약다항식이다. $d\in I$이므로 $uf+vg=d$인 표현도 존재한다. 모든 결합은 $d$의 배수이고, 이 표현에 임의의 다항식 $h$를 곱하면 $hd=(hu)f+(hv)g$이므로 $d$의 모든 배수는 결합이다. 따라서 $I=dK[x]$다. 이 증명은 체 위의 나머지 정리를 사용하며, 임의의 계수환에 대한 명제를 주장하지 않는다.

출처와 저작자 표시

다항식 확장은 2022-04-03에 0archlinux0 / MINJUN PARK이 게시하고 CC BY 4.0으로 표시한 Tistory ID 25에서 착안했다. 해당 원문은 다항식 명제를 언급하지만 그 페이지에서 증명하지 않는다. 위의 증명은 체 위에서 별도로 제시했다.