초등 숫자 이론(number theory)에서, 베주의 항등식(Bézout's identity, 역시 베주의 보조정리라고 불림)은 다음 정리(theorem)입니다:
a와 b를 최대 공통 약수(greatest common divisor) d를 갖는 정수(integer)라고 놓습니다. 그런-다음 ax + by = d를 만족하는 정수 x와 y가 존재합니다. 보다 일반적으로, 형식 ax + by의 정수는 정확히 d의 배수입니다.
(여기서 우리는 0과 0의 최대 공통 약수를 0으로 취급합니다.) 정수 x와 y는 (a, b)에 대해 베주 계수(Bézout coefficients)라고 불립니다; 그것들은 고유하지 않습니다. 베주 계수의 쌍은 확장된 유클리드 알고리듬(extended Euclidean algorithm)에 의해 계산될 수 있고, 이 쌍은 \(|x|\le | b/d |\) 및 \(|y|\le | a/d |\)를 만족하는 두 쌍 중 하나입니다 (상등은 오직 만약 a와 b 중 하나가 다른 것의 배수이면 발생할 수 있습니다).
예제로써, 15와 69의 최대 공통 약수는 3이고, 우리는 15 × (-9) + 69 × 2 = 3를 쓸 수 있습니다.
유클리드의 보조정리(Euclid's lemma) 또는 중국의 나머지 정리(Chinese remainder theorem)와 같은, 초등 숫자 이론에서 많은 다른 정리는 베주의 항등식의 결과로써 생깁니다.
베주 도메인(Bézout domain)은 베주의 항등식이 유지되는 정수 도메인(integral domain)입니다. 특히, 베주의 항등식은 주요 아이디얼 도메인(principal ideal domain)에서 유지됩니다. 베주의 항등식의 결과로서 생기는 모든 각 정리는 따라서 모든 이들 도메인에서 참입니다.
Structure of solutions
만약 a와 b가 둘 다 0이 아니고 한 쌍의 베주 계수 (x, y)가 (예를 들어, 확장된 유클리드 알고리듬(extended Euclidean algorithm)을 사용하여) 계산되면, 모든 쌍은 다음 형식으로 표현될 수 있습니다:
\(\quad\displaystyle \left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),\)
여기서 k는 임의의 정수, d는 a와 b의 최대 공통 약수이고, 분수는 정수로 단순화됩니다.
만약 a와 b가 둘 다 비-영이면, 이들 베주 계수 쌍 중 정확히 두 쌍은 다음을 충족합니다:
\(\quad\displaystyle |x| \le \left |\frac{b}{d}\right |\quad \text{and}\quad |y| \le \left |\frac{a}{d}\right |,\)
그리고 상등은 오직 만약 a와 b 중 하나가 남은 다른 것을 나누면 발생할 수 있습니다.
이것은 유클리드 나눗셈(Euclidean division)의 속성에 의존합니다: 두 개의 비-영 정수 c와 d가 주어지고, 만약 d가 c를 나누지 않으면, c = dq + r 및 0 < r < |d|를 만족하는 정확히 한 쌍 (q, r)이 있고, c = dq + r 및 -|d| < r < 0를 만족하는 또 다른 하나가 있습니다.
작은 베주의 계수의 두 쌍은 \(\frac{x}{b/d}\) 옆에 있는 두 정수 중 하나를 위의 공식에서 k에 대해 선택함으로써 주어진 하나의 (x, y)로부터 얻어집니다.
확장된 유클리드 알고리듬은 항상 이들 두 최소 쌍 중 하나를 생성합니다.
Example
a = 12 및 b = 42를 놓으면, gcd (12, 42) = 6입니다. 그런-다음 우리는 최소 쌍에 대해 빨간색으로, 나머지 다른 쌍에 대해 파란색으로 쓰인 베주 계수와 함께 다음과 같은 베주의 항등식을 가집니다.
\(\quad\displaystyle
\begin{align}
\vdots \\
12 &\times ({\color{blue}{-10}}) & + \;\; 42 &\times \color{blue}{3} &= 6 \\
12 &\times ({\color{red}{-3}}) & + \;\;42 &\times \color{red}{1} &= 6 \\
12 &\times \color{red}{4} & + \;\;42 &\times({\color{red}{-1}}) &= 6 \\
12 &\times \color{blue}{11} & + \;\;42 &\times ({\color{blue}{-3}}) &= 6 \\
12 &\times \color{blue}{18} & + \;\;42 &\times ({\color{blue}{-5}}) &= 6 \\
\vdots
\end{align}
\)
만약 (x, y) = (18, -5)가 베주 계수의 원래 쌍이면, \(\frac{18}{42/6} \in [2, 3]\)는 각각 k = 2, k = 3을를 통해 최소 쌍을 산출합니다: 즉, (18 - 2 ⋅ 7, -5 + 2 ⋅ 2) = (4, -1), 및 (18 - 3 ⋅ 7, -5 + 3 ⋅ 2) = (-3, 1)입니다.
Proof
임의의 비-영 정수 a와 b가 주어지면, \(S=\{ax+by \mid x,y\in\mathbb{Z} \text{ and } ax+by>0\}\)라고 놓습니다. 집합 S는 비-빈인데 왜냐하면 그것은 (x = ±1 및 y = 0와 함께) a 또는 –a 중 하나를 포함하기 때문입니다. S는 양의 정수의 비-빈 집합이므로, 그것은 바른-순서화 원리(well-ordering principle)에 의해 최소 원소 \(d = as + bt\)를 가집니다. d가 a와 b의 최대 공통 약수임을 입증하기 위해, 우리는 d가 a와 b의 공통 약수임과 임의의 다른 공통 약수 c에 대해, 우리가 c ≤ d를 가짐을 입증해야 합니다.
d에 의한 a의 유클리드 나눗셈(Euclidean division)은 다음과 같이 쓰일 수 있습니다:
\(\quad\displaystyle a=dq+r\quad\text{with}\quad 0\le r<d.\)
나머지 r은 \(S\cup \{0\}\)안에 있는데, 왜냐하면 다음이기 때문입니다:
\(\quad\displaystyle
\begin{align}
r & = a - qd \\
& = a - q(as+bt)\\
& = a(1-qs) - bqt.
\end{align}
\)
따라서 r은 형식 \(ax+by\)의 것이고, 그러므로 \(r\in S\cup \{0\}\)입니다. 어쨌든, 0 ≤ r < d이고, d가 S에서 가장-작은 양수입니다: 나머지 r은 따라서 S 안에 있지 않을 수 있으며, r을 반드시 0으로 만듭니다. 이것은 d가 a의 약수임을 의미합니다. 비슷하게 d는 역시 b의 약수이고, d는 a와 b의 공통 약수입니다.
이제, c를 a와 b의 임의의 공통 약수로 놓습니다: 즉, a = cu 및 b = cv를 만족하는 u와 v가 존재합니다. 우리는 따라서 다음을 가집니다:
\(\quad\displaystyle \begin{align}d&=as + bt\\
& =cus+cvt\\
&=c(us+vt).\end{align} \)
즉, c는 d의 약수이고, 따라서 c ≤ d입니다.
Generalizations
For three or more integers
베주의 항등식은 두 정수보다 많게 확장될 수 있습니다: 만약 다음이면
\(\quad\displaystyle \gcd(a_1, a_2, \ldots, a_n) = d\)
다음 식이
\(\quad\displaystyle d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n\)
다음 속성을 가짐을 만족하는 정수 \(x_1, x_2, ..., x_n\)가 있습니다:
- d는 이 형식의 가장-작은 양의 정수입니다.
- 이 형식의 모든 각 숫자는 d의 배수입니다.
For polynomials
베주의 항등식은 정수에 대해 같은 방법으로 필드(field)에 걸쳐 일변수 다항식(univariate polynomial)에 대해 작동합니다. 특히 베주의 계수와 최대 공통 약수는 확장된 유클리드 알고리듬(extended Euclidean algorithm)으로 계산될 수 있습니다.
두 다항식의 공통 근(root)이 최대 공약 약수의 근이므로, 베주의 항등식과 대수학의 기본 정리(fundamental theorem of algebra)는 다음 결과를 의미합니다:
필드에서 계수를 갖는 일변수 다항식 f와 g에 대해, af + bg = 1을 만족하는 다항식 a와 b가 존재하는 것과 f와 g가 임의의 대수적으로 닫힌 필드(algebraically closed field) (공통적으로 복소수(complex number)의 필드)에 공통 근을 가지지 않는 것은 필요충분 조건입니다.
이 결과를 임의의 숫자의 다항식과 불확정수로의 일반화는 힐베르트 영점-정리(Hilbert's Nullstellensatz)입니다.
For principal ideal domains
서론에서 언급했듯이, 베주의 항등식은 정수의 링(ring)에서 뿐만 아니라, 임의의 다른 주요 아이디얼 도메인(principal ideal domain) (PID)에서도 작동합니다. 즉, 만약 R이 PID, a와 b가 R의 원소이고, d가 a와 b의 최대 공통 약수이면, ax + by = d를 만족하는 R 안에 원소 x와 y가 있습니다. 그 이유는 아이디얼(ideal) Ra+Rb가 주요이고 Rd와 같기 때문입니다.
베주의 항등식이 유지되는 정수 도메인은 베주 도메인(Bézout domain)이라고 불립니다.
History
프랑스의 수학자(mathematician) 에티엔 베주(Étienne Bézout) (1730–1783)는 다항식에 대해 이 항등식을 입증했습니다. 어쨌든, 정수에 대해 이 명제는 이미 다른 프랑스 수학자, 클로드 가스파르 바셰 드 메지리아크 (Claude Gaspard Bachet de Méziriac) (1581–1638)의 연구에서 찾아질 수 있습니다.
External links
- Online calculator for Bézout's identity.
- Weisstein, Eric W. "Bézout's Identity". MathWorld.