📚 유클리드 호제법이란

➕ 유클리드 호제법(Euclidean algorithm)

유클리드 호제법 또는 유클리드 알고리즘은 두 개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

두 개의 자연수 a, b에 대해서 a 를 b 로 나눈 나머지를 r 이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. (단, a > b 일때)

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

➕ 증명

$a,b\in {\mathbb {Z}}$ 이고, ${\displaystyle a\geq b}a\geq b$ 라고 하자.
그러면, ${\displaystyle a=bq+r}$ 을 만족하는 유일한 정수 ${\displaystyle q,r}$ 이 존재한다. 이때, ${\displaystyle 0\leq r<b}$ 이다.

${\displaystyle \left(a,b\right)=d,a=d\alpha ,b=d\beta }$ 라고 하자. 즉, ${\displaystyle \alpha }$ 와 ${\displaystyle \beta }$ 는 서로소이다.

${\displaystyle a=bq+r.}$
${\displaystyle \Rightarrow d\alpha =d\beta q+r.}$
${\displaystyle \Rightarrow d|r.}$ (즉, $r$ 은 $d$ 의 배수)
이제, ${\displaystyle r=d\rho .}$ 라고 하자.

만약 ${\displaystyle \left(\beta ,\rho \right)=d'>1}$ 라면, ${\displaystyle \beta =d'\beta ',\rho =d'\rho '}$ 으로 두었을 때,

${\displaystyle a=bq+r.}$
${\displaystyle \Rightarrow d\alpha =d\beta q+d\rho =dd'\beta 'q+dd'\rho '=dd'\left(\beta 'q+\rho '\right).}$
${\displaystyle \Rightarrow \alpha =d'\left(\beta 'q+\rho '\right).}$ 이 되므로,
${\displaystyle d'|\alpha }$ 이다. (즉, $α$는 $d'$의 배수 )

즉, ${\displaystyle d'|\alpha ,d'|\beta }$ 가 되어 ${\displaystyle \alpha }$ 와 ${\displaystyle \beta }$ 는 서로소라는 것에 모순이다.

이는 ${\displaystyle \left(\beta ,\rho \right)=d'>1}$ 라는 가정에서 나타나는 모순이므로 ${\displaystyle \left(\beta ,\rho \right)=1}$ 이다.

따라서 곧 ${\displaystyle \left(b,r\right)=d}$ 라는 것이다.

💻 구현

public class Euclidean {

    private int a;
    private int b;

    public Euclidean(int a, int b){
        this.a = a;
        this.b = b;
    }

    public int getGreatestCommonDivision(){
        return gcdByRecursiveFunc(a, b);
    }
    
    public int getLeastCommonMultiple(){
        return a * b / gcdByRecursiveFunc(a, b);
    }

    // 반복문 사용
    private int gcdByLoop(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    // 재귀함수 사용
    private int gcdByRecursiveFunc(int a, int b){
        if(a % b == 0){
            return b;
        }
        return gcdByRecursiveFunc(b, a % b);
    }
}

사용 결과

public class Main {

    public static void main(String[] args) {
        int a = 18;
        int b = 16;

        System.out.println("두 수의 최대공약수는 " + new Euclidean(a, b).getGreatestCommonDivision() + " 입니다.");
        System.out.println("두 수의 최소공배수는 " + new Euclidean(a, b).getLeastCommonMultiple() + " 입니다.");
    }
}