최대공약수

유클리드 호제법

• 두 정수 $a,b$의 최대공약수를 구하는 알고리즘
• $a\geq b >0$라고 가정하자
• $r_{-1}=a, r_0=b$라 두고, 다음과 같은 나눗셈을 반복

$$ \begin{aligned} r_{-1}&=r_0q_0+r_1,\, 0<r_1<r_0 \\ r_{0}&=r_1q_1+r_2 ,\, 0<r_2<r_1 \\ \cdots \\ r_{n-1}&=r_{n}q_{n}+r_{n+1},\, 0<r_{n+1}<r_n \\ r_{n}&=r_{n+1}q_{n+1}\\ \end{aligned} $$

• 나눗셈을 반복하여 나머지가 0이 될 때, 얻어지는 $r_{n+1}$이 $a,b$의 최대공약수이다
• 이 때, $k=n+2$회의 나눗셈이 필요하며, $a\geq F_{k+1}=F_{n+3}$이 성립한다. 여기서 $F_k$는 피보나치 수열

$$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$

정리

두 자연수 $a\geq b>0$에 유클리드 호제법을 적용할 때 필요한 나눗셈의 회수 $k$에 대하여 다음이 성립한다 $$ k<2.08\log a+1.45 $$

베주 항등식

• 두 정수 $a,b$의 최대공약수 $\gcd(a,b)$에 대하여, 적당한 $x,y\in \mathbb{Z}$가 존재하여, 다음을 만족한다

$$ax+by=\gcd(a,b)$$

사전형태의 자료

• http://en.wikipedia.org/wiki/Bézout's_identity