1. 개념과 특징

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

• 두 수 또는 그 이상의 수에서 공통된 약수 중 가장 큰 수를 의미합니다.
• 예를 들어, 18과 24의 약수:
  • 18의 약수: {1, 2, 3, 6, 9, 18}
  • 24의 약수: {1, 2, 3, 4, 6, 8, 12, 24}
  • 공통된 약수: {1, 2, 3, 6} → 최대공약수(GCD) = 6

최소공배수(LCM, Least Common Multiple)

• 두 수 또는 그 이상의 수에서 공통된 배수 중 가장 작은 수를 의미합니다.

• 최소공배수는 다음 공식으로 계산할 수 있습니다.

  LCM(a,b)=a×bGCD(a,b)\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}

• 예를 들어, 18과 24의 최소공배수:

  • 18의 배수: {18, 36, 54, 72, …}
  • 24의 배수: {24, 48, 72, …}
  • 공통된 배수 중 가장 작은 값: 72 → 최소공배수(LCM) = 72

2. 유클리드 호제법 (Euclidean Algorithm)

• 최대공약수를 구하는 가장 효율적인 알고리즘 중 하나입니다.

• 두 수 와 에서 라고 가정할 때,

  aa

  bb

  a>ba > b

  • aa를 로 나눈 나머지를 이라 하면,

    bb

    rr

    GCD(a,b)=GCD(b,r)GCD(a, b) = GCD(b, r)

  • 이 과정을 나머지가 0이 될 때까지 반복하면 마지막 남은 수가 최대공약수(GCD) 입니다.

예제 (GCD(18, 24))

1. 24를 18로 나눈 나머지: (나머지 6)

   24÷18=124 \div 18 = 1

2. 18을 6으로 나눈 나머지: (나머지 0 → 종료)

   18÷6=318 \div 6 = 3

3. 마지막 남은 수 6이 GCD(18, 24) 입니다.

3. 코드 예제

1) Python 코드

# 최대공약수 (GCD) - 유클리드 호제법
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 최소공배수 (LCM)
def lcm(a, b):
    return (a * b) // gcd(a, b)  # LCM 공식 사용

# 테스트
a, b = 18, 24
print("GCD:", gcd(a, b))  # 6
print("LCM:", lcm(a, b))  # 72