[C 언어] 유클리드 호제법 증명과 재귀함수 구현

유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요.

 

유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다.

여담으로 최소공배수는 (두 수의 곱/gcd)를 하면 되기 때문에, 따로 구할 필요가 없고

 

세 수의 최대공약수를 구한다 해도 gcd(gcd(a,b),c)를 하면 되므로 두 수의 최대공약수를 구하는 알고리즘에 대해서만 알아도 충분할 겁니다.

 

 

우선 위의 사진에서 최대공약수를 구하는 알고리즘을 이해할 수 있고,

이는 단순히 r = a%b 에 대해서 gcd(a,b) = gcd(b,r)임을 보이면 됩니다.

 

 

증명은 위와 같습니다.

 

그래서 gcd함수 부분을 코드로 구현하면

 

int gcd(int a, int b)
{
	if(b == 0)
    {
    	return a;
    }
	return gcd(b,a%b);
}

 

이와 같은데, 저는 재귀가 보기도 편해서 이렇게 구현해서 사용합니다.

 

확장된 유클리드 알고리즘이라는 것도 있는데 이는 부정방정식의 해를 구할 때 사용합니다. 고등학생 때 확장된 유클리드 알고리즘으로 일차 선형 부정방정식을 게산하는걸 만들었는데 이젠 기억이 안 나네요..

 

감사합니다.