기초부터 되짚어보자.
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$이므로 해가 존재하지 않는다.
'수학 > 정수론' 카테고리의 다른 글
[정수론] 6. 중국인의 나머지 정리 (0) | 2022.04.21 |
---|---|
[정수론] 5. 고차 합동 방정식 (0) | 2022.04.20 |
[정수론] 4. 합동 (0) | 2022.04.17 |
[정수론] 3. 디오판투스 방정식 (0) | 2022.04.12 |
[정수론] 1. 피타고라스 세 수 (4) | 2022.04.06 |