베주 항등식

ax + by = gcd(a, b)를 성립하는 x, y는 항상 존재한다.

1. 집합 S = {ax + by > 0 | x, y는 정수}를 가정했을 때

   • S는 공집합이 아니므로,
     • y=0, x=1이면: a×1 + b×0 = a
     • a가 양수면 그대로, 음수면 |a| (x=-1로 조정)
     • 따라서 S는 최소한 하나의 원소를 가짐
   • S에 있는 가장 작은 원소를 d라고 불러볼 수 있다.

2. a를 d로 나누면 몫 q와 나머지 r로 표현할 수 있을 것이다.

   a = dq + r  (0 ≤ r < d)

   여기서 만약 r이 0보다 크다면

   r = a - dq
   = a - (as + bt)q
   = a(1-sq) + b(-tq)

   이므로 r도 S의 원소라는 뜻인데, r < d이므로 d가 최소원소라는 것에 모순된다.
   따라서 r = 0이어야 한다. 즉, a는 d로 나누어 떨어진다.
   같은 방법으로 b도 d로 나누어 떨어지는 것을 알 수 있다.

3. d는 a와 b의 공약수이면서, d = as + bt이다.

   만약 다른 공약수 c가 있다고 하면, c에 어떤 정수 l이나 k를 곱한 것이 a, b와 각각 같을 것이다.

   • a = c × l
   • b = c × k

   따라서 이렇게 표현할 수 있다.

   d = as + bt
   = c × l × s + c × k × t
   = c × (l * s + k * t)

   즉, c는 d의 약수이다.
   모든 공약수 c는 d의 약수여야하므로 d는 가장 큰 공약수, 다시 말해 최대공약수(gcd)이다.

4. 집합 S = {ax + by > 0 | x, y는 정수}의 가장 작은 원소 d는 a, b의 최대공약수이므로,
   ax + by = gcd(a, b)를 성립하는 x, y는 항상 존재한다.
   

이 식을 베주 항등식(Bézout’s Identity)이라 부른다.