정수론 | 기호 + 유클리드 호제법/확장 유클리드 알고리즘 알아가기

정수론 | 기호

 

$a|b$는 $b$가 $a$로 나누어 떨어진다는 뜻이다.

 

더불어 $a|b$는 $a$가 $b$의 약수라는 것을 의미한다.

 

유클리드 호제법

 

유클리드 호제법은 GCD ( GreatestCommonDivisor ) 알고리즘이라고도 불리우며

 

어떤 두 수 $a$와 $b$의 최대공약수를 구하는 알고리즘이다.

 

유클리드 호제법은 재귀적으로 실행되며 과정은 다음과 같다.

 

int gcd(int a, int b){

    int c;

    while(b){

         c=a%b;

         a=b;

         b=c;

    }

    return a;

}

 

확장 유클리드 알고리즘을 배우기 전에는 베주 항등식을 알아두어야 한다.  

베주 항등식

베주 항등식이란 식 $ax+by=g$ $(a,b$는 정수$)$ $(x,y)$ 정수 근에 대해 정수 해 $(x,y)$를 가지려면

 

$g=gcd(a,b)$이어야 한다는 성질을 가지고 있다.

 

확장 유클리드 알고리즘

 

확장 유클리드 알고리즘은 $a,b$가 정수일 때 $ax+by=gcd(a,b)\;(gcd(a,b)=g)$형태의 식의 해 $(x,y)$와 $gcd(a,b)$를 구하는 알고리즘이다.

 

이 식의 형태는 베주 항등식과 같다.

 

따라서 정수 해 $(x,y)$를 항상 가진다.

 

$a=bq+r$로 표현해보자.

 

그렇다면 식의 형태는 다음과 같을 것이다.

 

$(bq+r)x+by=g$

 

식을 정리하면 새로운 베주 항등식 꼴이 나온다.

 

$b(qx+y)+rx=g$

 

$x=y'$

 

$y+qx=x'$

 

$y=x'-qy'$

 

우리는 정수 해 $(x,y)$를

 

이러한 재귀적인 방법을 통해 구할수 있고,

 

$(y',x'-qy')$이 정수 해가 된다.

 

확장 유클리드 알고리즘의 종료 여부는 유클리드 알고리즘과 같이 $b=0$일 때이다.

 

$b=0$ 이되면 $ax+0*y=g$에서 최대공약수 $g$는 자연스레 $x=1$일때가 답이 되어 이때

 

$g=a,x=1,y=0$ 이 된다.

 

이를 재귀적으로 구현한 코드는 다음과 같다. (seastar105님의 구현 코드)

 

pair<int,pair<int,int>> xGCD(int a, int b) {   
    if(b == 0) return {a,{1,0}};
    pair<int,pair<int,int>> ret = xGCD(b, a%b);
    int g, x, y;
    g = ret.first;
    tie(x,y)=ret.second;
    return {g,{y,x-(a/b)*y}};  
}

 

확장 유클리드 알고리즘의 일반해는 다음과 같다.

 

$g,x_0,y_0=xGCD(a,b)$

 

$x=x_0+kb/g$

 

$y=y_0-ka/g$

 

 

 

참고 :

https://seastar105.tistory.com/64