[정수론](-)[LCM = ab/gcd(a, b)]

두 정수 a, b에 대해 최소공배수 lcm(a, b) = ab/gcd(a, b)임을 보이시오.

a, b의 어떤 공배수 d가 있다고 한다면
a|d, b|d여야 하고
최소공배수 lcm은 가장 작은 공배수이므로
모든 d에 대해 lcm(a, b)|d이어야 한다.

 

lcm(a, b) = ab/g라 하자. (g = gcd(a, b))
ab/g | d -> ab | dg
선형방정식의 정리에 의해 g = ax+by의 x, y를 항상 구할 수 있다. 따라서 해당 등식으로 바꾸면
ab | d(ax+by)
d는 a, b의 공배수이므로 d = am = bn (m, n은 정수)
ab | bnax + amby = ab | ab(nx + my) 이므로
따라서 모든 d를 ab/g가 나누므로 lcm(a, b) = ab/g다.