최대공약수와 최소공배수

• 정의
  • 최대공약수
  • 서로소, 상대소수
  • 최소공배수
• 정리
  • 최소공배수와 최대공약수의 곱
  • a,b의 최대공약수와 b,r의 최대공약수
• 유클리드 알고리즘
• 베주의 정리와 베주의 항등식
• 참고문헌
• Links

정의

최대공약수

GCD: The Greatest Common Divisor

Let \(a\) and \(b\) be integers, not both zero. The largest integer \(d\) such that \(d \vert a\) and \(d \vert b\) is called the greatest common divisor of \(a\) and \(b\). The greatest common divisor of \(a\) and \(b\) is denoted by \(gcd(a, b)\).

• 0 이 아닌 정수 a, b 에 대하여
  • \(d \vert a\) 이고 \(d \vert b\)인 가장 큰 정수 \(d\) 를 a, b의 최대공약수라 부른다.
• 최대공약수는 \(gcd(a, b)\) 로 표시된다.

참고: \(d \vert a\)는 \(a\)가 \(d\)로 나누어 떨어진다는 의미.

서로소, 상대소수

relatively prime

The integers \(a\) and \(b\) are relatively prime if their greatest common divisor is 1.

• 정수 a, b 의 최대공약수가 1 이면
  • a, b 는 서로소이다.
  • 서로소는 상대소수라고도 한다.

최소공배수

LCM: The Least Common Multiple

The least common multiple of the positive integers \(a\) and \(b\) is the smallest positive integer that is divisible by both \(a\) and \(b\). The least common multiple of \(a\) and \(b\) is denoted by \(lcm(a, b)\).

• 양의 정수 a, b 의 최소공배수는
  • a 와 b 로 나누어 떨어지는 가장 작은 양의 정수이다.
• 최소공배수는 \(lcm(a, b)\) 로 표시된다.

정리

최소공배수와 최대공약수의 곱

a,b의 최대공약수와 b,r의 최대공약수

Let \(a = bq + r\), where \(a, b, q\), and \(r\) are integers. Then \(gcd(a, b) = gcd(b, r)\).

• \(a,b,q,r\)이 정수이고 \(a = bq + r\) 이면
  • \(gcd(a, b) = gcd(b, r)\) 이다.

증명

\(d \vert a\) 이고, \(d \vert b\)라고 가정하자. (\(a\)와 \(b\)를 나누었을 때 나누어 떨어지는 수 \(d\) 가 있다고 가정하자)

그렇다면 \(a - bq\) 도 \(d\) 로 나누어 떨어질 것이다.

그런데 \(r = a - bq\) 이므로, \(r\) 은 \(d\)로 나누어 떨어진다.

따라서, \(a\) 와 \(b\) 의 모든 공약수는 \(b\)와 \(r\) 의 공약수이다.

한편, \(r = a - bq\) 에서 \(bq + r = a\) 이므로, \(b, r\)의 공약수는 \(a, b\)의 공약수이다.

그러므로 \(gcd(a,b) = gcd(b,r)\).

유클리드 알고리즘

The Euclidean Algorithm

• 유클리드 호제법이라고도 한다.
  • 互: 서로
  • 除: 나누는
  • 法: 알고리즘

다음은 go 언어로 작성한 유클리드 알고리즘이다.

func Gcd(a, b int) int {
    x := a
    y := b
    for y != 0 {
        r := x % y
        x = y
        y = r
    }
    return x
}

다음은 재귀를 사용한 것이다.

func Gcd(a, b int) int {
    if a < b {
        return Gcd(b, a)
    }
    if a%b == 0 {
        return b
    }
    return Gcd(b, a%b)
}

이런 방법도 있다.

func Gcd(a, b int) int {
    if b == 0 {
        return a
    }
    r := a % b
    return Gcd(b, r)
}

베주의 정리와 베주의 항등식

Bézout's theorem

If \(a\) and \(b\) are positive integers, then there exist integers \(s\) and \(t\) such that \(gcd(a, b) = sa + tb\).

• 양의 정수 \(a, b\) 에 대하여
  • \(gcd(a, b) = sa + tb\)를 만족하는 정수 \(s, t\) 가 존재한다.

Bézout’s identity

If \(a\) and \(b\) are positive integers, then integers \(s\) and \(t\) such that \(gcd(a, b) = sa + tb\) are called Bézout coefficients of \(a\) and \(b\) (after Étienne Bézout, a French mathematician of the eighteenth century). Also, the equation \(gcd(a, b) = sa + tb\) is called Bézout’s identity.

• 양의 정수 \(a, b\)에 대하여, \(gcd(a,b) = sa + tb\) 를 만족하는 정수 \(s, t\)를 \(a, b\)의 베주 계수라 부른다.
• 방정식 \(gcd(a, b) = sa + tb\)를 베주의 항등식이라 부른다.

GCD as Linear Combinations

베주 항등식에 의해 \(gcd(a,b)\)는 \(a, b\) 정수 계수를 갖는 선형결합으로 표현할 수 있다.

가령, \(gcd(24, 60) = 12\)이므로 \(s = -2, \ t = 1\) 이다.

숫자가 약간 커지면 유클리드 호제법을 사용하면 된다.

\(gcd(625442, 215326)\) 의 경우를 생각해 보자.

유클리드 호제법의 계산 과정을 참고해 적절히 대입하면 베주의 항등식으로 표현하기 용이하다.

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일

Links

• https://en.wikipedia.org/wiki/Greatest_common_divisor
• 베주 항등식(wikipedia)