GCD 및 LCM 계산기

최대공약수(GCF)라고도 하는 GCD는 두 숫자를 나머지가 없이 나누는 가장 큰 양의 정수입니다. 예를 들어 12와 18의 GCD는 6이므로 6이 두 수를 균등하게 나누는 가장 큰 수입니다.

LCM은 두 숫자로 나눌 수 있는 가장 작은 양의 정수입니다. 예를 들어 4와 6의 LCM은 12이므로 12는 4와 6으로 나눌 수 있는 가장 작은 수입니다.

두 개의 양의 정수 a와 b의 경우: GCD(a,b) × LCM(a,b) = a × b. 이 관계를 통해 GCD를 알고 있으면 LCM을 계산할 수 있고, 그 반대의 경우도 마찬가지입니다.

GCD는 분수 단순화(분자와 분모를 GCD로 나누기), 디오판틴 방정식 풀기, 암호화 및 컴퓨터 과학의 다양한 응용 분야에 필수적입니다.

분수를 단순화하려면 분자와 분모를 모두 GCD로 나눕니다. 예를 들어 24/36을 단순화하려면 GCD(24,36) = 12를 구한 다음 둘을 12로 나누어 2/3을 구합니다. 이렇게 하면 가장 낮은 조건의 분수가 나옵니다.

LCM은 반복되는 이벤트를 동기화할 때 사용됩니다. 예를 들어 두 버스가 동시에 도착하는 시간 찾기, 분수 추가를 위한 공통 분모 결정, 반복 작업 예약, 톱니 수가 다른 기어의 정렬 시기 계획 등이 있습니다.

각 숫자를 소인수로 나눈 다음, 소인수에 가장 낮은 거듭제곱을 곱합니다. 예를 들어 48 = 2^4 × 3, 18 = 2 × 3^2입니다. 공통 요인은 2^1과 3^1이므로 GCD = 2 × 3 = 6입니다.

각 숫자를 소인수로 나눈 다음 가장 큰 거듭제곱을 사용하여 모든 소인수를 곱합니다. 12 = 2^2 × 3 및 18 = 2 × 3^2의 경우 2^2와 3^2를 취하므로 LCM = 4 × 9 = 36이 됩니다.

유클리드 알고리즘은 나누고 나머지를 취하는 것을 반복하여 GCD를 효율적으로 찾습니다. GCD(48,18)의 경우: 48÷18=2 나머지 12, 18÷12=1 나머지 6, 12÷6=2 나머지 0. 나머지가 0인 경우 마지막 제수(6)가 GCD입니다.