베주 항등식
Bézout's Identity[1]
1. 개요
베주 항등식(Bézout's Identity)은 두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식이다. 그 내용은 다음과 같다.
위 세 명제 중 메인은 1번이며, 1번을 증명하는 과정에서 2번 명제와 3번 명제가 따라서 증명된다.
2. 증명
증명은 다음과 같은 순서로 진행된다. 자세한 과정은 아래에 있다.
2.1. 단계 1
둘 중 적어도 하나는 0이 아닌 정수 $$a$$, $$b$$가 있다. 이때 다음과 같은 집합 $$S$$를 정의하자.
$$S = \left\{ m | m = ax + by > 0, x \in \mathbb{Z}, y\in \mathbb{Z} \right\}$$
먼저 $$S \ne \varnothing$$임을 보이자. 만약 $$ a > 0$$라면 $$ \left| a \right| = a \times 1 + b \times 0 \in S$$이다. 만약 $$ a < 0$$라면 $$ \left| a \right| = a \times (-1) + b \times 0 \in S$$이다. 만약 $$ a = 0$$라면 $$ b \ne 0$$이라서 앞서 a의 경우와 같은 논리로 $$ \left| b \right| \in S$$ 이다. 따라서 집합 $$ S $$ 는 $$ \left| a \right|$$와 $$ \left| b \right|$$ 중 적어도 하나를 원소로 가지므로 $$S \ne \varnothing$$이다.
집합 $$S$$는 정의에 따라서 자연수의 부분집합이다. $$S \ne \varnothing$$이므로 자연수의 정렬성(Well-ordering Principle)[2]에 의해 집합 $$S$$는 가장 작은 원소를 가진다.
$$\therefore$$ 집합 $$S$$의 최소 원소, 즉 $$ax + by$$ 꼴로 나타낼 수 있는 가장 작은 자연수는 존재한다. 그것을 $$d$$라고 부르자.
2.2. 단계 2
$$S$$의 정의에 의해, 어떤 정수 $$k, l$$에 대하여 $$d = ak +bl$$이다.
나눗셈 정리에 의해, $$ S $$에 속하는 임의의 원소 $$ x $$ 에 대하여 $$ x = qd + r (0 \le r < d)$$라고 할 수 있다. 만약 $$ x $$ 가 $$ d$$의 배수가 아니라고 가정하자.[3] 그렇다면 나머지 $$ r $$ 은 0이 아닌 $$0 < r < d$$인 자연수이다. 그리고 $$ x $$ 는 집합 $$ S $$ 의 원소이므로 $$ x = au + bv, u \in \mathbb{Z} , v \in \mathbb{Z}$$ 라고 할 수 있다.
$$ r $$ 은 $$ x $$ 를 $$ d $$ 로 나누었을 때 나머지이므로 $$ d $$ 보다 작다. 앞서 $$ d $$ 를 집합 $$ S $$ 에서 가장 값이 작은 원소로 정의했음에도 $$ d $$ 보다 작은 $$ S $$ 의 원소인 $$ r $$ 이 존재하는 것은 $$ d $$의 최소성을 위반하므로 모순이다. 따라서 처음의 가정인 "$$ x $$ 가 $$ d $$ 의 배수가 아니다."는 거짓이다. 따라서 $$ x $$ 는 $$ d $$ 의 배수이다.
$$ x $$ 는 집합 $$ S $$ 의 임의의 원소이므로 집합 $$ S $$ 의 모든 원소는 $$ d $$ 의 배수이다. 따라서 $$ a $$ 혹은 $$ b $$ 가 0이 아닌 정수 일 경우 $$ |a| $$ 혹은 $$ |b| $$ 가 집합 $$ S$$의 원소이기 때문에 $$ d $$ 를 약수로 갖는다. 한편 $$ a $$ 혹은 $$ b $$ 가 0일 경우 0이 아닌 모든 수는 0의 약수이기 때문에 $$ d $$ 를 약수로 갖는다. 따라서 $$ d $$ 는 $$ a $$ 와 $$ b $$ 의 공약수이다.
2.3. 단계 3
만약 $$e$$가 $$a,b$$의 공약수라고 하자. $$ a=a'e, b = b'e$$이면 $$d = ak+bl = e(a'k+b'l)$$이므로, $$e$$는 $$d$$의 약수이다. 따라서 $$a,b$$의 모든 공약수는 $$d$$의 약수이므로, $$d$$는 약수 중에서 가장 큰 최대공약수이다.
3. 유클리드 호제법과의 연관성
유클리드 호제법을 수행한 뒤 그 과정을 따라가면 $$d = ax+by$$를 만족하는 정수 $$x, y$$를 직접 계산할 수 있는데, 이 알고리즘을 확장된 유클리드 호제법(extended Euclidean algorithm)이라 부르기도 한다. 유클리드 호제법이
$$ a = b q_1 + r_1, b = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, \cdots,$$
즉
$$a = r_{-1}, b = r_{0}, r_i = r_{i+1} q_i + r_{i+2} (0 \le r_{i+2} < r_{i+1}) $$
의 알고리즘으로 진행되고, 마지막에 $$r_n = \gcd(a,b)=d$$ (즉 $$r_{n+1} = 0$$)으로 종결되었다고 하자. 이 때 수열 $$x_i, y_i$$를 다음과 같이 귀납적으로 정의한다.
$$ (x_{-1}, y_{-1}) = (1,0), (x_0, y_0) = (0,1), (x_{i+2}, y_{i+2}) = (x_{i} - q_i x_{i+1}, y_i - q_i y_{i+1} ) $$
이렇게 정의하면 귀납법을 이용해 항상 $$ r_i = a x_i + b y_i$$가 됨을 보일 수 있고, 최종적으로 $$d = r_n = a x_n + b y_n $$을 얻을 수 있다.
항목 2의 증명을 보면 $$d=ax+by$$를 만족하는 정수 $$x,y$$가 존재한다는 것만 알려줄 뿐, 그 $$x,y$$를 계산하는 방법은 전혀 알려주지 않는다는 것에서 확장된 유클리드 호제법의 진가가 나온다. 알고리즘 정수론적인 관점에서 보면 그런 $$x,y$$를 실제로 계산하는 것은 잉여역수를 구하는 등 합동식 연산의 기초가 되기 때문에 중요하고, 또한 호제법 알고리즘의 시간 복잡도도 $$O( (\log a)^2 )$$로 (나눗셈 횟수만 고려하면 $$O(\log a)$$) 나름 괜찮으니만큼 훌륭한 필수 알고리즘인 것이다.
3.1. 예시
기호로 적으면 어려워 보이지만, '나머지를 a와 b의 일차결합으로 나타낸다'의 아이디어만 생각하면 손으로 계산하기도 생각보단 할만하다.
a = 6192, b = 1012
6192 = 6*1012 + 120, 120 = a - 6b
1012 = 8*120 + 52, 52 = 1012 - 8*120 = b - 8(a-6b) = -8a + 49b
120 = 2*52 + 16, 16 = 120 - 2*52 = (a-6b) - 2(-8a+49b) = 17a -104b
52 = 3*16 + 4, 4 = 52 - 3*16 = (-8a+49b) - 3(17a-104b) = -59a + 361b
gcd(a,b) = 4 = -59a + 361b
4. 일차 부정방정식과의 연관성
베주 항등식과 위의 확장된 유클리드 호제법은 다음 꼴의 일차 부정방정식을 완벽히 푸는 방법을 제공한다.
베주 항등식의 증명을 참고하면 방정식이 해가 존재할 필요충분조건은 $$c \in S$$의 여부이므로 바로 증명된다. 만약 $$d \vert c$$라면 확장된 유클리드 호제법으로 특수해를 구할 수 있다. 일반해에 대한 진술에 대해서는, $$(x',y')=(x-x_0,y-y_0)$$이 방정식 $$ax' + by'=0$$의 해여야 하는데, $$a/d, b/d$$는 서로소이므로 $$(b/d) \vert (a/d) x'$$에서 $$(b/d) \vert x'$$가 유도된다. (사실 이것도 베주 항등식을 이용한다.) $$x' = (-b/d)k$$로 놓으면 결론이 증명된다.
5. 확장
베주 항등식은 변수가 하나인 다항식에 대해서도 성립한다. 위의 $$a, b, d$$를 모두 최고차항이 1인(monic) 다항식으로 바꾸고, '가장 작은 자연수' 를 '차수가 가장 작은 다항식'으로 바꾸자. 물론 $$x,y$$는 monic일 필요는 없다. 다만 위의 증명은 유리수, 실수, 복소수 계수에서만 성립한다. 정확히는 계수가 체의 범위에 있을 때. 증명도 위와 거의 동일한데, $$S$$의 정의를 $$ax+by$$꼴의 모든 다항식으로 놓고, 차수가 가장 작은 monic 다항식을 $$d$$로 고르면 된다. 다항식에서도 나눗셈 정리가 나머지 정리라는 이름으로 그대로 먹히기 때문.
다항식 버전의 베주 항등식은 사실 교과과정에서 부분분수분해를 할 수 있는 암묵적인 근거가 된다. 정수론 버전의 베주 항등식은 유사하게 중국인의 나머지 정리의 근거가 되지만, 이건 교과에 안나오니까...
추상대수학 중 특히 환론을 안다면 단항이데알정역(PID)들이 베주 항등식을 만족시킨다는 것을 알 수 있는데, 단순히 이데알 $$S=(a,b)$$의 생성원을 $$d$$로 놓으면 된다. 나눗셈 정리와 유클리드 호제법이 성립하는 유클리드정역(ED)은 당연히 된다. 다만 역은 성립하지 않는데, 심지어는 유일인수분해정역(UFD)도 아닌데 베주 항등식은 되는 것들도 있다고 한다...
[1] 프랑스 수학자 에티엔 베주의 이름에서 따 왔다.[2] 자연수의 정렬성(Well-ordering Principle)이란 자연수 전체 집합의 부분집합 중 공집합이 아닌 집합은 값이 가장 작은 원소를 가진다는 원리이다. 첫 번째 원소를 가진다고 말해도 좋다. 자세한 증명은 ProofWiki를 참조하자.[3] 귀류법이 사용되고 있다.[4] 첫 번째 등호에서는 $$ x = qd + r $$에서 $$ qd $$ 를 이항하였다. 두 번째 등호에서는 $$ x $$ 에 $$ au + bv $$ 를 대입하고 $$ d $$ 에 $$ ak + bl $$ 을 대입하였다. 세 번째 등호에서는 분배법칙을 이용하여 전개한 후 항의 위치를 바꾸었다. 네 번째 등호에서는 $$ a $$ 와 $$ b $$ 를 인수로 가진 항끼리 묶어냈다. 그럼 $$ S $$ 의 정의에 따라 $$ r $$ 은 $$ S $$ 의 원소가 된다.