임의의 정수 $a$와 양의 정수 $b$에 대하여, 다음을 만족하는 정수 $q$(몫)와 $r$(나머지)이 유일하게 존재합니다.
이 정리는 정수의 웰-오더링 원리(Well-Ordering Principle)를 이용하여 증명됩니다.
두 정수 $a, b$를 동시에 나누는 가장 큰 정수를 $\gcd(a, b)$라고 합니다. 큰 수의 GCD를 효율적으로 구하는 방법이 바로 유클리드 알고리즘입니다.
$\gcd(a, b) = \gcd(b, r)$ 임을 이용합니다. ($a = bq + r$)
1. $a = bq_1 + r_1$ ($0 \le r_1 < b$)
2. $b = r_1q_2 + r_2$ ($0 \le r_2 < r_1$)
3. $r_1 = r_2q_3 + r_3 \dots$
나머지가 0이 되기 직전의 나머지가 바로 최대공약수입니다.
임의의 정수 $a, b$에 대하여, $\gcd(a, b) = d$라고 하면 다음을 만족하는 정수 $x, y$가 존재합니다.
이때 $d$는 $ax + by$ 꼴로 나타낼 수 있는 최소의 양의 정수입니다. 만약 $\gcd(a, b)=1$이면 두 수는 서로소(Relatively Prime)라고 합니다.
유클리드 알고리즘의 과정을 역으로 추적하여 베주 항등식의 계수 $x, y$를 직접 구할 수 있습니다.
문제: $\gcd(252, 198)$을 구하고, 이를 $252x + 198y$ 형태로 나타내시오.
1. $252 = 1 \times 198 + 54$
2. $198 = 3 \times 54 + 36$
3. $54 = 1 \times 36 + 18$
4. $36 = 2 \times 18 + 0 \implies \mathbf{\gcd = 18}$
역추적:
$18 = 54 - 1 \times 36$
$18 = 54 - 1 \times (198 - 3 \times 54) = 4 \times 54 - 1 \times 198$
$18 = 4 \times (252 - 1 \times 198) - 1 \times 198 = \mathbf{4(252) - 5(198)}$