최대공약수와 최소공배수

• 정의
  • 최대공약수
  • 서로소, 상대소수
  • 최소공배수
• 정리
  • 최소공배수와 최대공약수의 곱
  • 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)