GCD, LCM   Common Divisor, Greatest Common Divisor, Least Common Multipler   공약수, 최대공약수, 최소공배수

1. 공약수 (Common Divisor)

  ㅇ 여러 정수를 동시에 나눌 수 있는 정수


2. 최대 공약수 (Greatest Common Divisor) : gcd(a,b) = d

  ㅇ 공약수 중 가장 큰 정수

  ㅇ 최대공약수 gcd(a,b) = d 조건
     -  d ≥ 1
        . 최대공약수는 양의 정수
     -  d | a, d | b 
        . 최대공약수는 a,b의 공약수
     -  k | a 이고 k | b 이면,  k | d
        . a,b의 모든 공약수는 또한 최대공약수의 약수가 됨

  ㅇ 성질
     -  gcd(a,0) = a 는 항상 성립 
        . 0 이 아닌 모든 정수는 0 을 나눌 수 있으므로
     -  gcd(a,b) = 1 이면, a 및 b 는 서로소
        . (서로소 : 공통 인수를 갖지 않는 수) 

  ※ 최대공약수를 찾는 효율적인 방법은,  ☞ 유클리드 호제법 참조


3. 최소 공배수 (Least Common Multipler) : lcm(a,b)

  ㅇ 모두의 배수가 되는 최소의 자연수