최대공약수와 유클리드 호제법

최대공약수(Greatest Common Factor, Greatest Common Divisor)

말 그대로 공약수 중에서 최대인 수이다. 예컨대, 18의 약수는 1,2,3,6,9,18이고 54의 약수는 1,2,3,6,9,18,27,54이다. 이때 18과 54의 공통인 약수, 즉 공약수는 1,2,3,6,9,18이다. 이 공약수 중에서 가장 큰 18이 최대공약수이다.

 

최대공약수는 분수를 약분할 때 필요하다. 분모와 분자를 나눌 때 0이 아니라고 모두 나눌 수 있는 것은 아니다. 분모와 분자의 공약수이어야만 나눌 수 있다. 결국, 약분이란 분수의 분모와 분자를 두 수의 공약수로 나누는 것이다. 이때 공약수는 최대 공약수를 포함하는 것이므로 약분은 공약수로 나누는 방법과 최대공약수로 나누는 방법이 있다. 공약수로 약분하면 또 다른 공약수로 약분할 수 있다. 그래서 약분할 때는 공약수보다는 최대공약수로 나눈 것이 좋다. 왜냐하면 최대공약수로 나누면 더 이상 나눌 필요가 없는 기약분수가 되기 때문이다.

 

 

약수(Divisor)

약수는 어떤 수를 나누어떨어지게 하는 수를 말한다.

두 정수 a, b에 대하여 b = ac를 만족하는 정수 c가 존재한다면, a를 b의 약수라고 하며, 이를 a | b와 같이 표기한다.

 

기약분수(Irreducible Fraction)

기약분수는 분자와 분모의 공약수(Common Factor)가 1 뿐이어서 더 이상 약분 되지 않는 분수이다. 분자와 분모를 1 이외의 공통된 약수로 나누는 행위를 약분(Reduction of a fraction)이라고 한다. 정수 a, b에 대해, 분수 a/b가 기약분수라는 것과 a, b가 서로소 즉, 최대공약수가 1이라는 것은 같은 말이다. (약분이 더 이상 1 이외에 가능하지 않다는 뜻이다.)

 

기약분수는 소수와는 상관이 없다. 분자와 분모 간의 공약수가 1뿐인게 중요하다. 7/9, 5/12 이런 분수들도 기약분수이다.

 

예제 코드

public class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[] {gcd(n, m), lcm(n, m)};
        return answer;
    }
    
    int gcd(int n, int m)
    {
        int rest = n % m;
        if (rest == 0)
        {
            return m;
        }
        else
        {
            return gcd(m, rest);
        }
    }
    
    int lcm(int n, int m)
    {
        return (n * m) / gcd(n, m);
    }
}

 

최소공배수(Least Common Multiple)

말 그대로 공배수 중에서 최소인 수이다. 예컨대 4의 배수는 4, 8, 12, 16, 20 ...이고 6의 배수는 6, 12, 18, 24, 30...이다. 이때, 4와 6의 공통인 배수, 즉 공배수는 12, 24, 36 ...이다. 이 공배수 중에서 최소인 12가 바로 최소공배수이다.

 

최대공약수와 최소공배수의 관계

 

유클리드 호제법(Euclidean algorithm)

유클리드 호제법을 사용하면 보다 효율적으로 최대공약수를 구할 수 있다.

 

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단 a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r`를 구하고, 다시 r을 r`로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

유클리드 호제법의 과정은 다음과 같다.

• 큰 수를 작은 수로 나눈다
• 나누는 수를 나머지로 계속 나눈다.
• 나머지가 0이 나오면 나누는 수가 최대공약수이다.

1512와 1008의 최대공약수를 유클리드 호제법으로 풀어보면

 

1512 = 1008 * 1 + 504

1008 = 504 * 2 + 0

 

두 수의 최대공약수는 504이다.

 

유클리드 호제법 예제 코드

public int gcd(int a, int b)
{
    while(b > 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }

    return a;
}

// 간략화한 버전
public int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

 

a = 4, b = 6으로 예를 들어보면

• a = 4, b = 6
• a = 6, b = 4
• a = 4, b = 2
• a = 2, b = 0

 

b가 0이 되면서 a의 값 결과 2가 4와 6의 최대 공약수가 된다.

같이 읽으면 좋은 글

정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법

참조 사이트

[코딩 팁] 최대공약수 : 유클리드 호제법 원리

[최대공약수와 최소공배수] 구하는 방법 참 여러 가지다