유클리드 호제법 알아보기
유클리드 호제법이란? 양의 정수 $a, b$와 $a=bq+r$ 인 정수 $q, r$에 대해 $gcd(a, b) = gcd(b,r)$ 이다. (이때 $gcd(a,b)$는 $a, b$의 최대공약수이다.) 증명하기 유클리드 호제법을 이용해 두 양의 정수의 최대공약수 구하기 두 양의 정수 $a, b$에 대하여 $a$를 $b$로 나누면 $a=bq_1+r_1$, ($0 \leq r_1 < a$)를 만족시키는 정수 $q_1, r_1$이 존재한다. (1) $r_1 = 0$이라 하고 $b$를 $r_1$으로 나누면 $b=gcd(b,r_1) = gcd(a,b)$ 이다. (2) $r_1 \neq 0$이라 하고 $b$를 $r_1$으로 나누면 $b=q_2r_1 + r2$, ($0 \leq r_2 < r_1$)을 만족시키는 정수 ..
2023. 1. 12.
