| 최대공약수와 최소공배수 60과 48의 최대공약수는 좌측의 값들을 곱한 2 * 2 * 3 = 12 이고, 최소공배수는 12 * 5 * 4 = 240이다. 따라서, 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Lowest Common Multiple, LCM)를 곱한 값은 주어진 두 수의 곱과 같다는 식이 성립된다. | 최대공약수 구하기, 유클리드 호제법 유클리드 호제법이란 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로(互) 상대방 수를 나누어(除)서 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a가 b보다 클 때 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 ..