최대 공약수 계산기

1. 최대공약수(Greatest Common Divisor, 약칭 GCD)는 수학에서 중요한 개념으로, 두 개 이상의 정수가 공유하는 약수 중 가장 큰 것을 말합니다. 이 정수들은 서로 인접해 있을 필요는 없으며, 임의로 선택할 수 있습니다.

2. 최대공약수의 정의: 두 정수 a와 b(둘 다 0이 아님)에 대해, a와 b를 모두 나눌 수 있는 정수 c가 존재한다면, c는 a와 b의 공약수입니다. 모든 공약수 중에서 가장 큰 것을 최대공약수라고 합니다.

3. 최대공약수의 성질:

(1) 어떤 두 정수의 최대공약수는 유일하다.

(2) a가 b의 배수라면, a와 b의 최대공약수는 b이다.

(3) 서로소인 두 정수의 최대공약수는 1이다.

(4) 최대공약수는 1보다 크며, 두 수 중 더 작은 수보다 크지 않다.

4. 최대공약수의 계산 방법:

(1)、소인수 분해법: 각 수를 소인수의 곱으로 분해한 후, 모든 수에 공통된 소인수(각 소인수 중 가장 적게 나타나는 것을 선택)를 취하고, 마지막으로 이 소인수들을 곱하여 최대공약수를 구한다.

(2) 유클리드 알고리즘: 이는 두 양의 정수 a와 b(a>b)의 최대공약수가 a를 b로 나눴을 때의 나머지 c와 b의 최대공약수와 같다는 사실에 기반한 더 효율적인 방법이다. 재귀나 루프를 통해 빠르게 결과를 구할 수 있다.