정수론 (2) - 베주 항등식

저번에 최대공약수, 최소공배수, 그리고 유클리드 호제법에 대해 알아보았습니다. 저번 시간에 배운 내용을 바탕으로 이번에는 정수론의 가장 중요한 정리 중 하나인 베주 항등식에 대해 알아보겠습니다.

 

별 그리기

다음과 같이 12개의 점이 원형으로 찍혀 있습니다.

여기서 0부터 시작해 두 칸씩 건너 뛰어서 점을 이어보도록 하겠습니다.

위와 같은 육각형이 나오네요! 이 도형은 열 칸씩 건너 뛰어도 나옵니다. 한편 세 칸씩, 또는 아홉 칸씩 건너 뛰면 각각 아래와 같은 도형이 그려집니다.

한 칸, 다섯 칸, 일곱 칸, 또는 열한 칸씩 건너 뛰면 아래와 같은 도형이 나옵니다.

아래 표는 $a$칸씩 건너 뛰었을 때 나오는 도형을 정리한 표입니다.

$a$칸 건너뛰었을 때	도달하는 점의 위치
1, 5, 7, 11	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
2, 10	0, 2, 4, 6, 8, 10
3, 9	0, 3, 6, 9
4, 8	0, 4, 8
6	0, 6

이 표를 유심히 보면 한 가지 패턴을 찾을 수 있습니다. 바로 $a$칸씩 건너뛰는 것으로 도달하는 점들은 $\text{gcd}(a, 12)$의 배수라는 점입니다.

 

수직선 건너뛰기

왜 그런지 알아보기 전에, 또 다른 문제를 보도록 합시다. 아래와 같은 수직선 위에서, 제가 원점에 서 있습니다. 저는 앞뒤로 15칸, 또는 6칸씩 움직일 수 있습니다. 그러면 이 때, 제가 도달할 수 있는 점들은 어떤 점들일까요?

먼저 15칸을 간 뒤 6칸을 뒤로 가면, 저는 $15-6 = 9$칸을 갈 수 있습니다.

즉, 이 문제는 제가 앞뒤로 6칸, 9칸을 움직일 수 있을 때 어떤 점에 도달할 수 있는가와 동일한 문제입니다.

똑같이 9칸을 간 뒤 6칸을 뒤로 가면, 저는 $9-6=3$칸을 갈 수 있습니다. 즉, 이 문제는 제가 앞뒤로 3칸, 6칸을 움직일 수 있을 때 어떤 점에 도달할 수 있는가와 동일한 문제입니다.

그런데 여기서 6칸을 간 뒤 3칸을 뒤로 가면, 저는 $6-3=3$칸을 갈 수 있는데 저는 이미 3칸을 갈 수 있는 상태였습니다. 즉, 저는 3칸보다 더 조금 이동할 수는 없다는 결론이 나옵니다. 결국 제가 도달할 수 있는 점들은 3의 배수인 점들이 되겠네요.

 

혹시 이 과정이 익숙하게 느껴지지 않나요? 우리가 지금 한 것은 유클리드 호제법입니다.

$$\text{gcd}(a, b) = \text{gcd}(a, b-a)$$

유클리드 호제법에 의하면 한 수에서 다른 수를 빼는 과정을 두 수가 같아질 때까지 계속 반복하면 최종적으로 얻게 되는 수는 최대공약수입니다. 때문에 제가 최소로 이동할 수 있는 단위는 $\text{gcd}(6, 15)$가 되며, 제가 이동할 수 있는 점들은 3의 배수가 되는 것입니다.

 

결론: 앞뒤로 $a, b$칸씩 움직일 수 있다면, $\text{gcd}(a, b)$의 배수인 점들에만 도달할 수 있으며, $\text{gcd}(a, b)$의 배수인 점들은 모두 도달할 수 있다.

 

두 문제 연결짓기

그런데 수직선 건너뛰기 문제와 별 그리기 문제는 동일한 문제입니다. 이를 보기 위해서, 수직선을 아래와 같이 동그랗게 말아보겠습니다.

이렇게 말면, 앞뒤로 15만큼 움직이는건 한 바퀴를 도는 것이기 때문에 그냥 제자리에 있는 것입니다. 때문에 실제로 의미있는 것은 앞뒤로 6만큼 움직이는 것입니다. 상황이 별 그리기 문제와 동일합니다! 그러나 여전히 제가 움직일 수 있는 곳은 $\text{gcd}(15, 6)$의 배수입니다. 즉, $a$등분되어 있는 원 위에서 $b$칸씩 건너뛰어서 도달할 수 있는 지점은 $\text{gcd}(a, b)$의 배수라는 것이죠.

 

베주 항등식

수직선 건너뛰기 문제의 결론을 수식으로 멋들어지게 쓰면 아래와 같습니다.

 

$N, M$이 정수일 때 $aN + bM$의 가능한 값은 $\text{gcd}(a, b)$의 배수이며, 오직 이 값들만이 가능하다.

 

이 정리를 베주 항등식(Bezout's Identity)라고 합니다. 한편 별 그리기 문제와 수직선 건너뛰기 문제의 연관성을 통해 위 정리는 아래 정리와 동치임을 알 수 있습니다.

 

$N$이 정수일 때, $aN$을 $b$로 나눴을 때의 나머지의 가능한 값은 $\text{gcd}(a, b)$의 배수이며, 오직 이 값들만이 가능하다.

 

이 사실은 나중에 합동식에서의 나눗셈에 대해 탐구할 때 매우 중요하게 쓰일 것입니다.

 

수식적 증명

지금까지 우리는 베주 항등식이 왜 성립하는지 직관적으로 살펴보았습니다. 혹시 관심있는 분들을 위해 이 정리를 수식적으로도 증명해 보겠습니다. 먼저 아래와 같이 유클리드 호제법을 적용해 보겠습니다.

$$\begin{align*} a &= bx_1 + r_1 & &0<r_1<b \\ b &= r_1x_2 + r_2 & &0<r_2 < r_1 \\ r_1 &= r_2x_3 + r_3 & &0<r_3 < r_2 \\ &\vdots & &\vdots \\ r_{n-1} &= r_nx_{n+1} + r_{n+1} & &0<r_{n+1} < r_n \\ r_n &= r_{n+1}x_{n+2} \end{align*}$$

유클리드 호제법에 의해 $\text{gcd}(a, b) = r_{n+1}$입니다. 위 식에서 $r_{n+1} = r_{n-1} - r_n x_{n+1}$이므로, $p_{n-1}=1, p_n=-x_{n+1}$에 대하여 $r_{n+1}$은,

$$r_{n+1} = p_{n-1}r_{n-1} + p_nr_n$$

꼴로 쓸 수 있습니다. 마찬가지로 $r_n = q_{n-2}r_{n-2} + q_{n-1}r_{n-1}$의 꼴이기 때문에, 이를 $r_{n+1} = p_{n-1}r_{n-1} + p_nr_n$에 대입하면 $r_{n+1}$은

$$r_{n+1} = s_{n-1}r_{n-1} + s_{n-2}r_{n-2}$$

의 꼴로 쓸 수 있습니다. 우변의 차수가 1씩 줄었습니다. 이 과정을 계속 반복하면 결국 $r_{n+1} =\text{gcd}(a, b)= Na + Mb$의 꼴로 표현이 될 것입니다. 이로 증명이 완료되었습니다. (사실 이것보다 조금 더 디테일하게 들어가야 하는데, 핵심은 이 정도입니다. 가볍게 배우는 건데 너무 엄밀히 따지지는 말자고요ㅎㅎ)

 

저는 다음 글, 합동식에서 뵙도록 하겠습니다!