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

아무리 큰 수라도 두 수의 GCD는 두 수를 정수배해서 더한 식으로 표현할 수 있다고요? 예를 들어 $42$와 $30$의 최대공약수 6은 $42(-2)+30(3)$처럼 실제 계산식으로 만들 수 있습니다.

이 생각은 나중에 RSA 같은 암호 알고리즘에서 “역원”을 찾을 때도 쓰입니다. 최대공약수는 단지 “가장 큰 공약수”가 아니라, 두 정수를 정수배해서 더한 식으로 나타낼 수 있는 특별한 수이기도 합니다. 그 사실을 보여 주는 정리가 바로 베주 항등식입니다.

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인 두 정수의 관계입니다.

작은 실험: 최대공약수를 식으로 만들어 보기

먼저 작은 수부터 직접 확인해 봅시다.

$$42(-2)+30(3)=-84+90=6$$

그리고

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

입니다. 즉, 42와 30의 최대공약수 6은 두 수를 정수배해서 더한 식으로 실제로 나타납니다.

다른 예도 보겠습니다.

$$10(-3)+35(1)=5, \qquad \gcd(10,35)=5$$

이렇게 몇 번 확인해 보면 “최대공약수가 그냥 목록에서 찾는 값이 아니라, 원래 두 수로 다시 만들 수 있는 값”이라는 패턴이 보입니다.

패턴을 용어로 정리하면

정수 $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. $42x+30y$로 만들 수 있는 수

교재는 먼저 $a=42$, $b=30$을 골라 $42x+30y$가 어떤 값을 만들 수 있는지 표로 살펴봅니다. 아래 표는 $x=-3,-2,-1,0,1,2,3$과 $y=-3,-2,-1,0,1,2,3$을 넣어 얻은 값입니다.

$y\backslash x$	-3	-2	-1	0	1	2	3
-3	-216	-174	-132	-90	-48	-6	36
-2	-186	-144	-102	-60	-18	24	66
-1	-156	-114	-72	-30	12	54	96
0	-126	-84	-42	0	42	84	126
1	-96	-54	-12	30	72	114	156
2	-66	-24	18	60	102	144	186
3	-36	6	48	90	132	174	216

표에 나오는 모든 수는 6의 배수입니다. 이는 $42$와 $30$이 모두 6으로 나누어지므로

$$42x+30y=6(7x+5y)$$

이기 때문입니다. 더 주목할 점은 최대공약수 $6$도 표 안에 실제로 나타난다는 점입니다. 예를 들어

$$42(-2)+30(3)=6=\gcd(42,30)$$

입니다.

예시 2. 작은 방정식은 직접 해를 찾을 수 있다

수들이 작으면 해를 추측해서 찾을 수도 있습니다. 예를 들어

$$10x+35y=5$$

는

$$x=-3,\qquad y=1$$

을 넣으면

$$10(-3)+35(1)=5$$

가 됩니다. 또

$$7x+11y=1$$

은

$$x=-3,\qquad y=2$$

를 넣어도

$$7(-3)+11(2)=1$$

이고,

$$x=8,\qquad y=-5$$

를 넣어도

$$7(8)+11(-5)=1$$

입니다. 이처럼 같은 방정식도 정수해가 하나로 고정되지 않을 수 있습니다.

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

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

$$ax + by = 1$$

꼴이 됩니다.

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

실험: 손으로 계산하기

베주 항등식의 실제 계산은 유클리드 호제법을 거꾸로 따라가는 방식으로 이루어집니다. 교재의 핵심 예시는

$$22x+60y=\gcd(22,60)$$

입니다.

먼저 유클리드 호제법을 적용합니다.

$$60=2\times22+16$$ $$22=1\times16+6$$ $$16=2\times6+4$$ $$6=1\times4+2$$ $$4=2\times2+0$$

따라서

$$\gcd(22,60)=2$$

입니다. 이제 각 나머지를 원래 두 수의 식으로 되돌립니다. 계산을 보기 쉽게 하기 위해 $a=60$, $b=22$라고 쓰면,

$$16=a-2b$$

이고,

$$6=b-16=b-(a-2b)=-a+3b$$

입니다. 다음으로

$$4=16-2\times6$$

이므로

$$4=(a-2b)-2(-a+3b)=3a-8b$$

입니다. 마지막으로

$$2=6-4$$

이므로

$$2=(-a+3b)-(3a-8b)=-4a+11b$$

입니다. 다시 $a=60$, $b=22$를 대입하면

$$-4\cdot60+11\cdot22=2$$

입니다. 따라서 $22x+60y=2$의 해로 쓰면

$$22(11)+60(-4)=2$$

이므로

$$x=11,\qquad y=-4$$

입니다.

교재는 더 큰 예로

$$12453x+2347y=1$$

도 같은 방식으로 계산합니다. 유클리드 호제법과 역대입을 끝까지 수행하면

$$1=304\cdot12453-1613\cdot2347$$

을 얻습니다. 즉,

$$(x,y)=(304,-1613)$$

입니다. 큰 수에서도 원리는 같습니다. 유클리드 호제법으로 마지막 0이 아닌 나머지를 찾고, 그 나머지를 원래 두 수의 정수배의 합으로 되돌리면 됩니다.

패턴 발견

두 실험에서 중요한 패턴은 다음과 같습니다.

• 최대공약수는 단순히 목록에서 찾는 수가 아니라 $ax+by$ 꼴로도 나타납니다.
• 유클리드 호제법의 나머지 식을 거꾸로 대입하면 계수 $x,y$를 찾을 수 있습니다.
• 두 수가 서로소이면 $ax+by=1$인 정수 $x,y$가 존재합니다.
• 베주 계수는 하나로 고정되지 않지만, 하나의 계수쌍만 찾아도 정리의 의미를 확인할 수 있습니다.

손계산의 핵심은 "마지막 0이 아닌 나머지"를 원래 두 수의 식으로 되돌리는 것입니다.

이론 정리

베주 항등식

정수 $a,b$가 모두 0이 아니면, $ax + by = \gcd(a,b)$를 만족하는 정수 $x,y$가 존재합니다.

특히 $\gcd(a,b)=1$이면 $ax + by = 1$인 정수해가 존재합니다.

Python으로 확인하기

확장 유클리드 알고리즘을 짧게 구현하면 베주 계수를 직접 확인할 수 있습니다.

from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return abs(a), 1 if a > 0 else -1, 0

    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

for a, b in [(42, 30), (10, 35), (7, 11), (22, 60), (12453, 2347)]:
    g, x, y = extended_gcd(a, b)
    print(f"{a}({x}) + {b}({y}) = {a*x + b*y}, gcd={g}")
    assert a * x + b * y == gcd(a, b)

출력된 $x,y$가 손으로 찾은 계수와 다를 수 있습니다. 그래도 $ax+by=\gcd(a,b)$를 만족하면 올바른 베주 계수입니다.

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차 디오판토스 방정식이 언제 정수해를 가지는지 살펴보겠습니다.