[정수론 입문 시리즈 6편] 베주 항등식은 최대공약수를 어떻게 식으로 보여 줄까?

지난 글에서는 유클리드 호제법으로 최대공약수를 빠르게 구하는 방법을 봤습니다. 그런데 정수론은 여기서 한 걸음 더 나아갑니다. 최대공약수는 단지 “가장 큰 공약수”가 아니라, 두 정수를 정수배해서 더한 식으로 나타낼 수 있는 특별한 수이기도 합니다. 그 사실을 보여 주는 정리가 바로 베주 항등식입니다.

What this post covers

• 베주 항등식이 무엇인지 설명합니다.
• 왜 $\gcd(a,b)$가 $ax+by$ 꼴로 표현되는지 이해합니다.
• 간단한 예시로 실제 계수를 찾는 과정을 봅니다.
• 이 정리가 다음 글의 1차 디오판토스 방정식과 어떻게 연결되는지 정리합니다.

이번 글에서 새로 나오는 용어

• 베주 항등식 (Bézout's Identity): 두 정수 $a,b$의 최대공약수는 $ax+by$ 꼴로 표현할 수 있다는 정리입니다.
• 1차 디오판토스 방정식 (Linear Diophantine Equation): 미지수의 정수해를 찾는 $ax+by=c$ 꼴의 방정식입니다.
• 최대공약수 (Greatest Common Divisor): 두 정수가 공통으로 가지는 약수들 가운데 가장 큰 수입니다.
• 서로소 (Coprime): 최대공약수가 1인 두 정수의 관계입니다.

베주 항등식은 무엇을 말하는가?

정수 $a$, $b$가 모두 0이 아니라고 합시다. 그러면 어떤 정수 $x$, $y$가 존재해서

$$ax + by = \gcd(a,b)$$

가 됩니다.

이 문장이 베주 항등식입니다.

겉으로 보면 단순한 식 같지만, 의미는 꽤 큽니다. 최대공약수는 단순히 약수를 나열해서 찾는 값이 아니라, 두 정수를 정수 계수로 섞어서 만들 수 있는 수라는 뜻이기 때문입니다.

여기서 $ax+by$는 $a$와 $b$를 정수배해서 더한 식입니다. 처음 보면 추상적으로 느껴질 수 있지만, 실제로는

• $12(-1) + 18(1)$
• $30(-1) + 18(2)$

처럼 익숙한 정수 계산을 일반식으로 쓴 것에 가깝습니다.

왜 이런 식이 중요할까?

베주 항등식은 정수론에서 자주 나오는 세 가지 질문을 한 번에 이어 줍니다.

1. 두 수의 최대공약수는 무엇인가?
2. 그 최대공약수를 식으로 만들 수 있는가?
3. 어떤 식 $ax+by=c$가 정수해를 가지는가?

즉, 최대공약수를 구하는 문제와 정수해를 찾는 문제가 따로 떨어져 있지 않다는 점을 보여 줍니다. 다음 글에서 볼 $ax+by=c$ 문제는 바로 이 연결 위에 서 있습니다.

유클리드 호제법과 어떻게 연결될까?

유클리드 호제법은 반복해서

$$a = bq + r$$

꼴을 만들며 나머지를 줄여 갑니다. 이 과정을 거꾸로 따라가면 마지막에 얻은 $\gcd(a,b)$를 원래의 $a$, $b$의 식으로 다시 표현할 수 있습니다.

즉,

• 앞으로 가면 최대공약수를 구하고
• 뒤로 돌아오면 최대공약수를 $ax+by$ 꼴로 쓸 수 있습니다.

이렇게 유클리드 호제법과 베주 항등식은 한 세트로 움직입니다.

예시 1. 12와 18

먼저

$$\gcd(12,18) = 6$$

입니다.

이제 6을 12와 18의 식으로 써 보겠습니다.

예를 들어

$$18 - 12 = 6$$

이므로

$$6 = 18 \times 1 + 12 \times (-1)$$

입니다.

즉,

$$12(-1) + 18(1) = 6$$

이 되어 베주 항등식이 실제로 성립함을 볼 수 있습니다. 물론 이것만이 유일한 표현은 아닙니다. 베주 항등식에서는 이런 계수쌍이 여러 개 나올 수 있습니다.

예시 2. 30과 18

먼저 유클리드 호제법으로 최대공약수를 구해 보겠습니다.

$$30 = 18 \times 1 + 12$$ $$18 = 12 \times 1 + 6$$ $$12 = 6 \times 2 + 0$$

따라서

$$\gcd(30,18) = 6$$

입니다.

이제 거꾸로 올라가면

$$6 = 18 - 12 \times 1$$

이고, 또

$$12 = 30 - 18 \times 1$$

이므로

$$6 = 18 - (30 - 18) = 2 \times 18 - 30$$

입니다.

즉,

$$6 = 30(-1) + 18(2)$$

로 쓸 수 있습니다. 이 과정이 바로 “유클리드 호제법으로 최대공약수를 구한 뒤, 그 계산을 거꾸로 따라가 계수를 찾는다”는 말의 실제 모습입니다.

서로소일 때는 무엇이 달라질까?

만약 두 수가 서로소라면 최대공약수가 1입니다. 그러면 베주 항등식은

$$ax + by = 1$$

꼴이 됩니다.

이 사실은 이후 합동과 모듈러 연산에서 매우 중요해집니다. 어떤 수가 모듈러 세계에서 역원을 가지는지 판단할 때도 결국 서로소 조건이 등장하기 때문입니다.

Common mistakes

1. 계수가 하나만 있다고 생각하는 실수

베주 항등식의 $x,y$는 보통 하나로 고정되지 않습니다. 한 쌍을 찾으면 그로부터 다른 해들도 많이 나옵니다.

2. 아무 수나 $ax+by$ 꼴로 된다고 생각하는 실수

$ax+by$ 꼴로 만들 수 있는 수들은 결국 $\gcd(a,b)$와 깊게 연결됩니다. 다음 글에서 보겠지만, $ax+by=c$가 정수해를 가지려면 $c$가 $\gcd(a,b)$의 배수여야 합니다.

3. 유클리드 호제법과 별개로 외우는 실수

베주 항등식은 유클리드 호제법과 분리된 정리가 아닙니다. 최대공약수를 구한 뒤, 그 계산을 거꾸로 되짚으면 계수를 찾을 수 있습니다.

Wrap-up

이번 글에서는 베주 항등식을 통해 최대공약수가 단순한 수가 아니라 $ax+by$ 꼴로 표현되는 구조라는 점을 정리했습니다. 특히 유클리드 호제법을 거꾸로 따라가면 실제 계수를 찾을 수 있다는 점이 핵심입니다.

다음 글에서는 이 결과를 바로 사용해서, $ax+by=c$ 꼴의 1차 디오판토스 방정식이 언제 정수해를 가지는지 살펴보겠습니다.