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

     (수정일:2013-11-07)

  1. 공약수(Common Divisor)
    1. 여러 정수를 동시에 나눌 수 있는 정수
  2. 최대 공약수 (Greatest Common Divisor) : gcd(a,b) = d
    1. 공약수 중 가장 큰 정수
    2. 최대공약수 gcd(a,b) = d 조건
      1. d ≥ 1
        1. 최대공약수는 양의 정수
      2. d | a, d | b
        1. 최대공약수는 a,b의 공약수
      3. k | a 이고 k | b 이면, k | d
        1. a,b의 모든 공약수는 또한 최대공약수의 약수가 됨
    3. 성질
      1. gcd(a,0) = a 는 항상 성립
        1. 0 이 아닌 모든 정수는 0 을 나눌 수 있으므로
      2. 서로소 : 공통 인수를 갖지 않는 수
        1. gcd(a,b) = 1 이면, a 및 b 는 서로소
  3. 최소 공배수 (Least Common Multipler) : lcm(a,b)
    1. 모두의 배수가 되는 최소의 자연수

[소수,최대공약수]
1. 소수, 합성수 2. 최대공약수 3. 소인수 분해

       최근수정이력     PC 화면