본문으로 건너뛰기

1. 기본 개념 정리​

1.1 최대공약수(GCD)​

  • 정의: 두 수의 공통된 약수 중 가장 큰 수
  • 표기: gcd(a,b)
  • 성질:
    • gcd(a,b) = gcd(b,a)
    • gcd(a,0) = |a|
    • gcd(a,1) = 1

1.2 최소공배수(LCM)​

  • 정의: 두 수의 공통된 배수 중 가장 작은 양의 정수
  • 표기: lcm(a,b)
  • 성질:
    • lcm(a,b) = lcm(b,a)
    • lcm(a,0) = 0
    • lcm(a,1) = |a|

1.3 GCD와 LCM의 관계​

a × b = gcd(a,b) × lcm(a,b)
  • 두 양의 정수 a, b에 대해 위와 같은 관계가 성립합니다
  • 이 관계가 성립하는 이유를 소인수분해를 통해 살펴보겠습니다.
a = p₁^α₁ × p₂^α₂ × ... × pₙ^αₙ
b = p₁^β₁ × p₂^β₂ × ... × pₙ^βₙ
  • 먼저 두 수 a, b를 소인수분해합니다
  • 여기서 p₁, p₂, ..., pₙ은 소수이며, α₁, α₂, ..., αₙ와 β₁, β₂, ..., βₙ는 0 이상의 정수입니다.
gcd(a,b) = p₁^min(α₁,β₁) × p₂^min(α₂,β₂) × ... × pₙ^min(αₙ,βₙ)
  • 최대공약수(GCD)는 각 소인수의 지수 중 작은 것을 선택합니다
lcm(a,b) = p₁^max(α₁,β₁) × p₂^max(α₂,β₂) × ... × pₙ^max(αₙ,βₙ)
  • 최소공배수(LCM)는 각 소인수의 지수 중 큰 것을 선택합니다
a × b = (p₁^α₁ × p₂^α₂ × ... × pₙ^αₙ) × (p₁^β₁ × p₂^β₂ × ... × pₙ^βₙ)
     = p₁^(α₁+β₁) × p₂^(α₂+β₂) × ... × pₙ^(αₙ+βₙ)
  • 두 수를 곱하면 각 소인수의 지수를 더한 값이 됩니다
gcd(a,b) × lcm(a,b) = (p₁^min(α₁,β₁) × ... × pₙ^min(αₙ,βₙ)) × (p₁^max(α₁,β₁) × ... × pₙ^max(αₙ,βₙ))
                    = p₁^(min(α₁,β₁)+max(α₁,β₁)) × ... × pₙ^(min(αₙ,βₙ)+max(αₙ,βₙ))
                    = p₁^(α₁+β₁) × p₂^(α₂+β₂) × ... × pₙ^(αₙ+βₙ)
  • GCD와 LCM을 곱하면 최종적으로 두 수의 곱과 같아집니다
min(x,y) + max(x,y) = x + y
  • 두 수 x, y에 대해 min(x,y) + max(x,y) = x + y가 성립합니다
  • 따라서 GCD와 LCM의 곱은 두 수의 곱과 같습니다
팁

이 관계식을 이용하면 GCD를 구한 후 LCM을 쉽게 계산할 수 있습니다:

lcm(a,b) = |a × b| ÷ gcd(a,b)

2. 유클리드 호제법​

2.1 기본 원리​

gcd(a,b) = gcd(b, a mod b)
  • 두 양의 정수 a, b에 대해 위와 같은 관계가 성립합니다
  • 이를 유클리드 호제법이라고 합니다

3. 수학적 증명​

3.1 귀류법을 이용한 증명​

  • A와 B의 최대공약수(GCD)가 G라고 할 때, A = aG, B = bG로 표현할 수 있습니다.
    • G가 최대 공약수이므로 a와 b는 서로소입니다.
  • 유클리드 호제법을 증명하기 위해 gcd(A,B) = G라고 가정했을 때 gcd(B,r) = G임을 증명하면 됩니다.
    • 여기서 r은 A를 B로 나눈 나머지입니다.
  • 나눗셈 정리에 의해 A = qB + r이라 하면, r = (a-qb)G가 됩니다.
    • q: A를 B로 나눈 몫
    • r: A를 B로 나눈 나머지
  • r = (a-qb)G이고 B = bG이므로 (a-qb)와 b가 서로소임을 증명하면 됩니다.
    • (a-qb)와 b가 서로소이면 B와 r의 최대공약수가 G이기 때문입니다.
  • (a-qb)와 b가 서로소임을 증명하기 위해 귀류법을 사용해보겠습니다.
    • (a-qb)와 b가 서로서가 아니라면 공약수 p가 존재하고, a - qb = np, b = mp라고 표현할 수 있습니다.
    • 이를 정리하면 a = (nq+m)p가 됩니다.
    • a = (nq+m)p, b = np가 되어 a와 b가 p를 공약수로 가진다는 모순이 발생합니다. (a와 b는 서로소이므로)
    • 따라서 귀류법에 의해 (a-qb)와 b는 서로소입니다.
  • 따라서 gcd(A,B) = G일 때 gcd(B,r) = G임을 증명했습니다.

4. 여러 수의 GCD와 LCM​

4.1 세 수 이상의 GCD 성질​

  • 결합법칙이 성립: gcd(a,gcd(b,c)) = gcd(gcd(a,b),c)
  • 교환법칙이 성립: gcd(a,b) = gcd(b,a)
  • n개 수의 GCD는 어떤 순서로 계산해도 동일

4.2 여러 수의 LCM 성질​

  • 결합법칙이 성립: lcm(a,lcm(b,c)) = lcm(lcm(a,b),c)
  • 교환법칙이 성립: lcm(a,b) = lcm(b,a)
  • GCD와 마찬가지로 계산 순서는 결과에 영향을 주지 않음