베주 항등식

3. 해의 구조

''a''와 ''b''가 모두 0이 아니고, 베주 계수 (''x'', ''y'')가 계산되었다면 (예를 들어 확장 유클리드 알고리즘을 사용하여), 모든 쌍은 다음과 같은 형태로 나타낼 수 있다.

:(''x'' - ''k''(''b''/''d''), ''y'' + ''k''(''a''/''d''))

여기서 ''k''는 임의의 정수, ''d''는 ''a''와 ''b''의 최대공약수이며, 분수는 정수로 약분된다.

만약 ''a''와 ''b''가 모두 0이 아니고 서로소라면, 베주 계수 쌍 중 정확히 두 쌍이 |''x''| < |''b''/''d''| 와 |''y''| < |''a''/''d''|를 만족한다. 확장 유클리드 알고리즘은 항상 이 두 최소 쌍 중 하나를 생성한다.

3. 1. 예시

4. 증명

주 아이디얼 정역^한국어 ''R''에서 원소 ''a''와 ''b''가 주어졌고, ''d''가 ''a''와 ''b''의 최대공약수 가운데 하나라고 하자. 그러면 다음 등식을 만족하는 원소 ''m''과 ''n''이 ''R''에 존재한다.

: ''ma'' + ''nb'' = ''d''

(주 아이디얼 정역에 대한 증명) ''R''가 주 아이디얼 정역이고, ''a'', ''b'' ∈ ''R''이며, ''d'' ∈ ''R''가 이들의 최대공약수 중 하나라고 하자. ''R''는 주 아이디얼 정역이므로 ''Ra'' + ''Rb''는 주 아이디얼이다. 즉,

: ''Ra'' + ''Rb'' = ''Rc''

인 ''c'' ∈ ''R''가 존재한다. 최대공약수의 정의에 따라

: ''Ra'' + ''Rb'' ⊂ ''Rd'' ⊂ ''Rc'' = ''Ra'' + ''Rb''

가 성립한다. 따라서

: ''Ra'' + ''Rb'' = ''Rd''

이고,

: ''ma'' + ''nb'' = ''d''

를 만족하는 ''m'', ''n'' ∈ ''R''가 존재한다.

(정수에 대한 증명) 0이 아닌 임의의 정수 ''a''와 ''b''에 대해, 집합 ''S'' = {''ax'' + ''by'' | ''x'', ''y'' ∈ '''Z''', ''ax'' + ''by'' > 0}를 정의하자. ''S''는 ''a'' 또는 -''a''를 포함하므로 공집합이 아니다(''x'' = ±1, ''y'' = 0일 때). ''S''는 양의 정수로 이루어진 공집합이 아닌 집합이므로, 정렬 원리에 의해 최소 원소 ''d'' = ''as'' + ''bt''를 갖는다.

''d''가 ''a''와 ''b''의 최대공약수임을 보이려면, ''d''가 ''a''와 ''b''의 공약수이고, 임의의 다른 공약수 ''c''에 대해 ''c'' ≤ ''d''임을 보이면 된다.

''a''를 ''d''로 유클리드 나눗셈하면 다음과 같이 나타낼 수 있다.

: ''a'' = ''dq'' + ''r'' (여기서 0 ≤ ''r'' < ''d'')

나머지 ''r''은 ''S'' ∪ {0}에 속한다. 왜냐하면,

: ''r'' = ''a'' - ''qd'' = ''a'' - ''q''(''as'' + ''bt'') = ''a''(1 - ''qs'') - ''bqt''

이므로, ''r''은 ''ax'' + ''by'' 꼴이기 때문이다. 따라서 ''r'' ∈ ''S'' ∪ {0}이다. 그런데 0 ≤ ''r'' < ''d''이고 ''d''는 ''S''에서 가장 작은 양의 정수이므로, ''r''은 ''S''에 속할 수 없고, 따라서 0이어야만 한다. 이는 ''d''가 ''a''의 약수임을 뜻한다. 마찬가지로, ''d''는 ''b''의 약수이므로, ''d''는 ''a''와 ''b''의 공약수이다.

이제 ''c''를 ''a''와 ''b''의 임의의 공약수라고 하자. 그러면 ''a'' = ''cu''와 ''b'' = ''cv''를 만족하는 ''u''와 ''v''가 존재한다. 따라서 다음이 성립한다.

: ''d'' = ''as'' + ''bt'' = ''cus'' + ''cvt'' = ''c''(''us'' + ''vt'')

즉, ''c''는 ''d''의 약수이다. ''d'' > 0이므로, ''c'' ≤ ''d''이다.^[5]

5. 일반화

베주 항등식은 셋 이상의 정수에 대해서도 확장할 수 있다. 만약 gcd(a₁, a₂, ..., aₙ) = d라면, 다음을 만족하는 정수 x₁, x₂, ..., xₙ이 존재한다.

:d = a₁x₁ + a₂x₂ + ⋯ + aₙxₙ

이는 다음과 같은 성질을 갖는다.

• d는 이 형태의 가장 작은 양의 정수이다.
• 이 형태의 모든 수는 d의 배수이다.

6. 역사

프랑스의 수학자 에티엔 베주(1730–1783)는 이 항등식을 다항식에 대해 증명했다.^[1] 정수에 대한 명제는 이보다 앞서 프랑스 수학자 클로드 가스파르 바셰 드 메지리악(1581–1638)의 저작에서 찾아볼 수 있다.^[2][3][4] 바셰는 서로소인 두 수가 주어졌을 때, 한쪽의 배수가 다른 쪽의 배수보다 1 큰 최소 배수를 찾는 문제를 연구했다.^[9]

참조

_[1] 서적 Théorie générale des équations algébriques https://archive.org/[...] Ph.-D. Pierres
_[2] 서적 Galois' Theory of Algebraic Equations World Scientific
_[3] 서적 Problèmes plaisants & délectables qui se font par les nombres http://www.bsb-muenc[...] Pierre Rigaud & Associates
_[4] 간행물 Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany http://hal.inria.fr/[...] 2009-02
_[5] 문서 以上の証明は{{Harvtxt|石井|2013|pp=26-32}}によった。
_[6] 서적
_[7] 서적
_[8] 서적
_[9] 서적
_[10] 간행물