정의

최대공약수

GCD: The Greatest Common Divisor

Let and be integers, not both zero. The largest integer such that and is called the greatest common divisor of and . The greatest common divisor of and is denoted by .

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

참고: 는 가 로 나누어 떨어진다는 의미.

서로소, 상대소수

relatively prime

The integers and 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 and is the smallest positive integer that is divisible by both and . The least common multiple of and is denoted by .

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

정리

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

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

Let , where , and are integers. Then .

  • 이 정수이고 이면
    • 이다.

증명

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

그렇다면 도 로 나누어 떨어질 것이다.

그런데 이므로, 은 로 나누어 떨어진다.

따라서, 와 의 모든 공약수는 와 의 공약수이다.

한편, 에서 이므로, 의 공약수는 의 공약수이다.

그러므로 .

유클리드 알고리즘

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)
}

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

Bézout’s theorem

If and are positive integers, then there exist integers and such that .

  • 양의 정수 에 대하여
    • 를 만족하는 정수 가 존재한다.

Bézout’s identity

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

  • 양의 정수 에 대하여, 를 만족하는 정수 를 의 베주 계수라 부른다.
  • 방정식 를 베주의 항등식이라 부른다.

GCD as Linear Combinations

베주 항등식에 의해 는 정수 계수를 갖는 선형결합으로 표현할 수 있다.

가령, 이므로 이다.

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

의 경우를 생각해 보자.

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

참고문헌

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

Links