최대공약수란 무엇입니까?

최대공약수는 두 입력 수를 나머지 없이 나누는 가장 큰 수입니다. 예를 들어 최대공약수(12, 18) = 6인데, 6은 12와 18을 모두 나눕니다.

최소공배수란 무엇입니까?

최소공배수는 두 입력 수의 배수인 가장 작은 수입니다. 예를 들어 최소공배수(12, 18) = 36인데, 36은 12와 18 모두로 나누어지는 가장 작은 수입니다.

유클리드 알고리즘은 반복된 나눗셈과 나머지 계산을 통해 최대공약수를 계산하는 효율적인 방법입니다: 최대공약수(a, b) = 최대공약수(b, a mod b)(b = 0이 될 때까지). 큰 수에서는 소인수분해보다 훨씬 빠릅니다.

이들은 다음 공식으로 연관됩니다: 최대공약수(a, b) × 최소공배수(a, b) = a × b. 이 항등식은 최대공약수를 알고 있을 때 최소공배수를 계산하는 데 유용합니다.

서로소 수(또는 상대적으로 소수)의 최대공약수는 1입니다. 이는 1 외에 공통 인수가 없다는 의미입니다. 예를 들어 최대공약수(7, 11) = 1입니다.

유클리드 알고리즘을 사용한 무료 최대공약수 및 최소공배수 계산기입니다. 단계별 설명과 함께 두 값을 찾아보세요.

두 수의 최대공약수와 최소공배수를 계산하세요.

GCD (a, b) = Euclidean algorithm; LCM (a, b) = \frac{a \times b}{GCD ( a , b )}