[include(틀:정수론)]
[목차]

Bézout's Identity[* 프랑스 수학자 [[https://ko.wikipedia.org/wiki/%EC%97%90%ED%8B%B0%EC%97%94_%EB%B2%A0%EC%A3%BC|에티엔 베주]]의 이름에서 따 왔다.]

== 개요 ==
베주 항등식(Bézout's Identity)은 두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식이다. 그 내용은 다음과 같다.

||적어도 둘 중 하나는 0이 아닌 정수 [math(a, b)]가 있다. 그리고 [math(a)]와 [math(b)]의 최대공약수를 [math(d)]라고 하자. 이때, 다음 세 명제가 성립한다.
1. [math(d= ax + by)] 를 만족하는 정수 [math(x, y)]가 반드시 존재한다.
2. [math(d)]는 정수 [math(x, y)]에 대하여 [math(ax+by)] 형태로 표현할 수 있는 가장 작은 자연수이다.
3. 정수 [math(x, y)]에 대하여 [math(ax+by)] 형태로 표현되는 모든 정수는 [math(d)]의 배수이다.||

위 세 명제 중 메인은 1번이며, 1번을 증명하는 과정에서 2번 명제와 3번 명제가 따라서 증명된다.

== 증명 ==
증명은 다음과 같은 순서로 진행된다. 자세한 과정은 아래에 있다.
||1.  [math(ax + by)] 꼴로 표현할 수 있는 가장 작은 자연수가 존재함을 밝힌다. 그것을 [math( d)] 라고 하자.
2. [math( d )]는  [math( a)]와  [math( b )]의 공약수임을 밝힌다.
3. [math( a)]와  [math( b )]의 공약수는 [math( d )]의 약수가 되어야 함을 밝힌다.||

=== 단계 1 ===
둘 중 적어도 하나는 0이 아닌 정수 [math(a)], [math(b)]가 있다. 이때 다음과 같은 집합 [math(S)]를 정의하자.

[math(S = \left\{ m | m = ax + by > 0, x \in \mathbb{Z}, y\in \mathbb{Z} \right\})]

먼저 [math(S \ne \varnothing)]임을 보이자. 만약 [math( a > 0)]라면 [math( \left| a \right| = a \times 1 + b \times 0 \in S)]이다. 만약  [math( a < 0)]라면 [math( \left| a \right| = a \times (-1) + b \times 0 \in S)]이다. 만약 [math( a = 0)]라면 [math( b \ne 0)]이라서 앞서 a의 경우와 같은 논리로 [math(   \left| b \right|  \in S)] 이다. 따라서 집합 [math( S )] 는  [math( \left| a \right|)]와 [math( \left| b \right|)] 중 적어도 하나를 원소로 가지므로 [math(S \ne \varnothing)]이다.

집합 [math(S)]는 정의에 따라서 자연수의 부분집합이다. [math(S \ne \varnothing)]이므로 자연수의 정렬성(Well-ordering Principle)[* 자연수의 정렬성(Well-ordering Principle)이란 자연수 전체 집합의 부분집합 중 공집합이 아닌 집합은 값이 가장 작은 원소를 가진다는 원리이다. 첫 번째 원소를 가진다고 말해도 좋다. 자세한 증명은 [[https://proofwiki.org/wiki/Well-Ordering_Principle|ProofWiki]]를 참조하자.]에 의해 집합 [math(S)]는 가장 작은 원소를 가진다.

[math(\therefore)] 집합 [math(S)]의 최소 원소, 즉 [math(ax + by)] 꼴로 나타낼 수 있는 가장 작은 자연수는 존재한다. 그것을 [math(d)]라고 부르자.

=== 단계 2 ===
[math(S)]의 정의에 의해, 어떤 정수 [math(k, l)]에 대하여 [math(d = ak +bl)]이다.

[math( S )]에 속하는 임의의 원소 [math( x )] 에 대하여 만약 [math( x )] 가 [math( d)]의 배수가 아니라고 가정하자.[* [[귀류법]]이 사용되고 있다.] [[나눗셈 정리]]에 의해, [math( x = qd + r (0 \le r < d))]라고 할 수 있다. 그렇다면 나머지 [math( r )] 은 0이 아닌 [math(0 < r < d)]인 자연수이다. 그리고 [math( x )] 는 집합 [math( S )] 의 원소이므로 [math( x = au + bv, u \in \mathbb{Z} , v \in \mathbb{Z})] 라고 할 수 있다.

||[math(r = x - qd = (au + bv) - q(ak + bl) = au - aqk + bv - bql = a(u - qk) + b(v - ql) \in S)] [* 첫 번째 등호에서는 [math( x = qd + r )]에서 [math( qd )] 를 이항하였다. 두 번째 등호에서는 [math( x )] 에 [math( au + bv )] 를 대입하고 [math( d )] 에 [math( ak + bl )] 을 대입하였다. 세 번째 등호에서는 분배법칙을 이용하여 전개한 후 항의 위치를 바꾸었다. 네 번째 등호에서는 [math( a )] 와 [math( b )] 를 인수로 가진 항끼리 묶어냈다. 그럼 [math( S )] 의 정의에 따라 [math( r )] 은 [math( S )] 의 원소가 된다.]||

[math( r )] 은 [math( x )] 를 [math( d )] 로 나누었을 때 나머지이므로 [math( d )] 보다 작다. 앞서 [math( d )] 를 집합 [math( S )] 에서 가장 값이 작은 원소로 정의했음에도 [math( d )] 보다 작은 [math( S )] 의 원소인 [math( r )] 이 존재하는 것은 [math( d )]의 최소성을 위반하므로 모순이다. 따라서 처음의 가정인 "[math( x )] 가 [math( d )] 의 배수가 아니다."는 거짓이다. 따라서 [math( x )] 는 [math( d )] 의 배수이다. 

[math( x )] 는 집합 [math( S )] 의 임의의 원소이므로 집합 [math( S )] 의 모든 원소는 [math( d )] 의 배수이다. 따라서 [math( a )] 혹은 [math( b )] 가 0이 아닌 정수 일 경우 [math( |a| )] 혹은 [math( |b| )] 가 집합 [math( S)]의 원소이기 때문에 [math( d )] 를 약수로 갖는다. 한편 [math( a )] 혹은 [math( b )] 가 0일 경우 0이 아닌 모든 수는 0의 약수이기 때문에 [math( d )] 를 약수로 갖는다. 따라서 [math( d )] 는 [math( a )] 와 [math( b )] 의 공약수이다.
=== 단계 3 ===
만약 [math(e)]가 [math(a,b)]의 공약수라고 하자. [math( a=a'e, b = b'e)]이면 [math(d = ak+bl = e(a'k+b'l))]이므로, [math(e)]는 [math(d)]의 약수이다. 따라서 [math(a,b)]의 모든 공약수는 [math(d)]의 약수이므로, [math(d)]는 약수 중에서 가장 큰 최대공약수이다.

== [[유클리드 호제법]]과의 연관성 ==
[[유클리드 호제법]]을 수행한 뒤 그 과정을 따라가면 [math(d = ax+by)]를 만족하는 정수 [math(x, y)]를 직접 계산할 수 있는데, 이 알고리즘을 확장된 유클리드 호제법(extended Euclidean algorithm)이라 부르기도 한다. 유클리드 호제법이
[math( a = b q_1 + r_1, b = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, \cdots,)]
즉
[math(a = r_{-1}, b = r_{0}, r_i = r_{i+1} q_{i+2} + r_{i+2} (0 \le r_{i+2} < r_{i+1}) )]
의 알고리즘으로 진행되고, 마지막에 [math(r_n = \gcd(a,b)=d)] (즉 [math(r_{n+1} = 0)])으로 종결되었다고 하자. 이 때 수열 [math(x_i, y_i)]를 다음과 같이 귀납적으로 정의한다.
[math( (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} ) )]
이렇게 정의하면 귀납법을 이용해 항상 [math( r_i = a x_i + b y_i)]가 됨을 보일 수 있고, 최종적으로 [math(d = r_n = a x_n + b y_n )]을 얻을 수 있다.

항목 2의 증명을 보면 [math(d=ax+by)]를 만족하는 정수 [math(x,y)]가 존재한다는 것만 알려줄 뿐, 그 [math(x,y)]를 계산하는 방법은 전혀 알려주지 않는다는 것에서 확장된 유클리드 호제법의 진가가 나온다. 알고리즘 정수론적인 관점에서 보면 그런 [math(x,y)]를 실제로 계산하는 것은 잉여역수를 구하는 등 [[합동식]] 연산의 기초가 되기 때문에 중요하고, 또한 호제법 알고리즘의 [[시간 복잡도]]도 [math(O( (\log a)^2 ))]로 (나눗셈 횟수만 고려하면 [math(O(\log a))]) 나름 괜찮으니만큼 훌륭한 필수 알고리즘인 것이다.

=== 예시 ===
기호로 적으면 어려워 보이지만, '나머지를 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
== 일차 [[부정방정식]]과의 연관성 ==
베주 항등식과 위의 확장된 유클리드 호제법은 다음 꼴의 일차 부정방정식을 완벽히 푸는 방법을 제공한다.
||정수 [math(a,b,c (a^2+b^2>0))]에 대해, 방정식 [math(ax + by = c)]가 정수해를 가질 필요충분조건은 [math(d=\gcd(a,b))]가 [math(c)]를 나누는 것이다. 만약 방정식이 특수한 해 [math((x_0,y_0))]을 가진다면, 방정식의 모든 해는 정수 [math(k)]에 대해 [math((x,y)=(x_0,y_0) + k(-b/d, a/d))] 꼴로 나타나진다.||
베주 항등식의 증명을 참고하면 방정식이 해가 존재할 필요충분조건은 [math(c \in S)]의 여부이므로 바로 증명된다. 만약 [math(d \vert c)]라면 확장된 유클리드 호제법으로 특수해를 구할 수 있다. 일반해에 대한 진술에 대해서는, [math((x',y')=(x-x_0,y-y_0))]이 방정식 [math(ax' + by'=0)]의 해여야 하는데, [math(a/d, b/d)]는 서로소이므로 [math((b/d) \vert (a/d) x')]에서 [math((b/d) \vert x')]가 유도된다. (사실 이것도 베주 항등식을 이용한다.) [math(x' = (-b/d)k)]로 놓으면 결론이 증명된다.

== 확장 ==
베주 항등식은 변수가 하나인 [[다항식]]에 대해서도 성립한다. 위의 [math(a, b, d)]를 모두 최고차항이 1인(monic) 다항식으로 바꾸고, '가장 작은 자연수' 를 '차수가 가장 작은 다항식'으로 바꾸자. 물론 [math(x,y)]는 monic일 필요는 없다. 다만 위의 증명은 유리수, 실수, 복소수 계수에서만 성립한다. 정확히는 계수가 [[체(대수학)|체]]의 범위에 있을 때. 증명도 위와 거의 동일한데, [math(S)]의 정의를 [math(ax+by)]꼴의 모든 다항식으로 놓고, 차수가 가장 작은 monic 다항식을 [math(d)]로 고르면 된다.[* 이러한 다항식이 두 개 이상일 경우 차수가 더 작은 다항식을 만들어낼 수 있기 때문에 이러한 다항식은 유일하다] 다항식에서도 [[나눗셈 정리]]가 [[나머지 정리]]라는 이름으로 그대로 먹히기 때문.

다항식 버전의 베주 항등식은 사실 교과과정에서 [[부분분수분해]]를 할 수 있는 암묵적인 근거가 된다. 정수론 버전의 베주 항등식은 유사하게 [[중국인의 나머지 정리]]의 근거가 되지만, 이건 교과에 안나오니까...

추상[[대수학]] 중 특히 환론을 안다면 단항이데알정역(PID)들이 베주 항등식을 만족시킨다는 것을 알 수 있는데, 단순히 이데알 [math(S=(a,b))]의 생성원을 [math(d)]로 놓으면 된다. [[나눗셈 정리]]와 [[유클리드 호제법]]이 성립하는 유클리드정역(ED)은 당연히 된다. 다만 역은 성립하지 않는데, 심지어는 유일인수분해정역(UFD)도 아닌데 베주 항등식은 되는 것들도 있다고 한다...

[[분류:정수론]][[분류:대수학]]