[정수론] 2. 유클리드 호제법

기초부터 되짚어보자.

1. $m \mid n$ : m은 n을 나눈다.

2. $\gcd (a,b)$ : a,b의 최대공약수

3. 소수는 $1$과 자기 자신만으로 나누어 떨어지는 수

4. 나머지정리 : $a = qb + r$ $(0 \le r < b)$

 

유클리드 호제법

$\gcd (a,b)$를 쉽고 빠르게(?) 구하는 방법이다.

$a_1 = a, a_2 = b$라고 하자.

나머지 정리에 따르면

$a_1 = q_1a_2 + a_3$

$a_2 = q_2a_3 + a_4$

$\dots$

$a_n = q_na_{n+1}$

같이 언젠가 나머지가 없어지는 때가 온다.

이때 $a_{n+1} = \gcd (a,b)$이다.

$2a_{i+2} \le a_{i} $이기 때문에 $log$시간 안에 구할 수 있다.

 

예를들어 $\gcd(132, 432)$를 구해보자

$432 = 3\times 132 + 36$

$132= 3\times 36 + 24$

$36 = 1\times 24 + 12$

$24 = 2\times 12$

$\gcd(132,432) = 12$

 

이것을 거꾸로 하면 $\gcd(x,y) = ax+by$꼴로 나타낼 수 있다. (모두 정수)

$12 = 36 - 1\times 24$

$ = 36-1\times (132-3\times 36)$

$=4\times 36 - 1 \times 132$

$=4\times (432 - 3 \times 132) - 1 \times 132$

$=4\times 432 - 13\times 132$

$a=4, b=-13$을 얻었다.

 

이 과정을 사용해서 백준 확장 유클리드 호제법태그가 있는 문제를 해결할 수 있다.

 

또한 위 과정에서 했던 것은 $ax+by = \gcd(a,b)$인 정수계수 방정식을 해결하는 방법이라고 볼 수 있다.

고등학교때 부정 방정식이라고 본 기억이 있는데 이를 정수범위로 좁힌것이다.

만약 $ax+by=c$가 정수 해를 가지려면 $\gcd(a,b) \mid c$를 만족해야 한다.

 

$432x+132y = 12$가 $x=4, y= -13$이었다.

$432x+132y = 24$를 풀어보면 우선 해를 가질 조건을 만족하고 위 방정식에서 해에 2를 곱하면 된다.

$432x+132y = 13$은 $\gcd(432,132) = 12 \nmid 13$이므로 해가 존재하지 않는다.