정수론 (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$의 꼴로 표현이 될 것입니다. 이로 증명이 완료되었습니다. (사실 이것보다 조금 더 디테일하게 들어가야 하는데, 핵심은 이 정도입니다. 가볍게 배우는 건데 너무 엄밀히 따지지는 말자고요ㅎㅎ)
저는 다음 글, 합동식에서 뵙도록 하겠습니다!
