최대 공약수 계산기

최대 공약수(GCD) 개념의 정의를 진행하기 전에 일반적으로 공약수가 무엇인지 이해해야 합니다.

정수가 여러 약수를 가질 수 있다는 것은 알려져 있습니다. 우리는 여러 정수에 의한 동시 액세스에 관심이 있습니다. 여러 정수의 공약수는 지정된 계열의 각 숫자에 대한 약수 역할을 할 수 있는 숫자로 간주합니다.

예를 들어, 숫자 8과 12의 공약수는 1과 4입니다. 이는 수학식을 작성하여 쉽게 확인할 수 있습니다. 8 = 4 ⋅ 2; 12 = 3 · 4.

각 숫자는 처음에 최소 2개의 공약수를 갖는다는 점에 유의해야 합니다. 모든 숫자는 나머지 없이 자체적으로 나누어질 수 있으며 1로도 나눌 수 있습니다.

최대 공약수 결정

두 자연수의 최대 공약수(GCD)는 두 자연수를 나눌 수 있는 자연수 중 가장 큰 수입니다. 두 자연수의 최대 공약수 값이 1이면 이 숫자를 서로소(coprime)라고 합니다.

두 수 a와 b에 대해 최대 공약수는 a와 b를 나머지 없이 나눌 수 있는 수입니다. 이 식은 다음과 같이 작성됩니다: gcd (a, b) = c.

GCD를 작성하는 또 다른 방법: (a, b) = c. 그러나 대부분의 경우 첫 번째 옵션이 사용됩니다.

예를 들어 숫자 4와 16의 최대 공약수는 4입니다. gcd(4, 16) = 4라고 작성해 보겠습니다.

이 결과에 도달한 방법을 설명하겠습니다.

숫자 4의 모든 약수를 적었습니다. 결과는 4, 2, 1입니다.
다음으로 16의 모든 약수를 그렸습니다. 16, 8, 4, 2, 1이 나왔습니다.
우리는 4와 16 모두에 공통인 약수를 선택했습니다. 우리는 4, 2, 1을 얻었습니다.
공약수 결과에서 가장 큰 것을 선택했습니다. 이것은 4입니다.
답을 얻습니다: 숫자 4와 16의 경우 GCD는 4입니다.

마찬가지로 세 개 이상의 정수에 대한 GCD를 찾을 수 있습니다. 이 경우 제안된 시리즈의 모든 숫자를 나눌 수 있는 가장 큰 정수가 됩니다.

예를 들어 정수 6, 12, 18, 42의 가장 큰 약수는 숫자 6, 즉 gcd(6, 12, 18, 42) = 6이 됩니다. 답은 알고리즘을 사용하여 얻었습니다. 위에서 설명한 것과 유사하게 시리즈의 숫자에 대해 모든 약수를 순차적으로 기록한 다음 가장 큰 약수가 선택되었습니다.

GCD 속성

최대 공약수는 약수가 0보다 큰 양의 정수의 GCD와 관련된 여러 속성을 가집니다.

속성 1

숫자의 위치를 변경해도 GCD의 최종 값은 변경되지 않습니다. 이 진술은 다음과 같이 작성할 수 있습니다.

gcd(a, b) = gcd(b, a).

속성 2

a가 b로 나누어지면 a와 b의 공약수 집합은 b의 약수 집합과 같습니다. 다음과 같이 작성되었습니다.

gcd(a, b) = b.

증명된 최대 약수 속성은 두 숫자 중 하나가 다른 숫자로 나누어질 때 두 숫자의 gcd를 찾는 데 사용할 수 있습니다. 이 경우 GCD는 다른 숫자를 나눌 수 있는 이러한 숫자 중 하나와 같습니다.

예:

gcd(12, 4) = 4.

유사:

gcd(10, 1) = 1.

속성 3

만약 a = bq + c, 여기서 a, b, c, q는 정수이면 a와 b의 공약수 집합은 b와 c의 공약수 집합과 같습니다.

gcd(a, b) = gcd(b, c) 등식이 유효합니다.

속성 4

gcd(ma, mb) = m ⋅ gcd(a, b) 식은 m이 임의의 자연수인 경우 참입니다.

속성 5

p가 a와 b의 공약수라고 가정해 봅시다.

gcd(a / p, b / p) = gcd(a, b) / p.

p = gcd(a, b)인 경우 다음을 얻습니다.

gcd (a / gcd (a, b), b / gcd (a, b)) = 1,

따라서 숫자 a/gcd(a, b)와 b/gcd(a, b)는 서로소입니다.

속성 6

두 개의 숫자는 적어도 하나의 공통 약수를 가집니다. 이것이 바로 숫자 1입니다.

일반적인 분수로 작업하려면 GCD 개념의 이론적 기초에 대한 지식과 그 정의에 대한 실용적인 기술이 필요합니다. 또한 GCD는 최소 공약수인 다른 수학적 단위와 밀접한 관련이 있습니다. 두 가지 정의는 일반적으로 표준 학교 커리큘럼의 일부로 학습됩니다.

최대 공약수(gcd)를 찾는 것은 상당히 인기 있는 작업입니다. 이 작업은 일반 분수가 나타나는 계산을 수행하는 데 도움이 됩니다.

GCD를 찾는 방법

최대 공약수를 찾는 몇 가지 요령이 있습니다. 가장 인기있는 것을 고려할 것입니다.

소인수로 숫자를 분해하여 GCD 찾기

이 방법은 수학 문제를 푸는 데 가장 자주 사용되는 방법 중 하나입니다.

소인수로 분해하여 GCD를 결정하는 알고리즘은 다음 단계로 구성됩니다.

숫자를 소인수로 나타냅니다. 예를 들어 숫자 20은 2 ⋅ 2 ⋅ 5의 곱으로 나타낼 수 있습니다.
두 확장 모두에 나타날 요소를 선택합니다.
이 요인들의 곱을 찾으십시오.

실제로 이 알고리즘을 적용한 몇 가지 예를 살펴보겠습니다.

숫자 12와 8의 GCD를 구하세요.

12와 8을 소인수로 분해:

<리>12 = 2 ⋅ 2 ⋅ 3. <리>8 = 2 ⋅ 2 ⋅ 2.

우리는 두 확장팩에 어떤 요소가 있는지 살펴봅니다. 찾기: 2와 2.

인수를 곱하고 다음을 얻습니다.

<리>2 ⋅ 2 = 4.

정답: gcd(12, 8) = 4.

숫자 75와 150의 GCD를 구하세요.

솔루션 순서는 이전 예와 유사합니다.

75와 150을 소인수로 표현해 보겠습니다.

<리>75 = 3 · 5 · 5. <리>150 = 2 · 3 · 5 · 5.

두 확장에서 반복되는 인수를 결정합니다: 3, 5, 5.

결과 숫자를 곱합니다: 3 ⋅ 5 ⋅ 5 = 75.

정답: gcd(75, 150) = 75.

숫자 9와 5의 GCD를 구하세요.

이 예에서는 승수가 1일 수 있는 소수를 사용합니다.

9와 5를 소인수로 분해할 때 동일한 약수가 아님을 알 수 있습니다.

<리>5 = 5. <리>9 = 3 · 3.

이 사건은 특별하다는 것을 기억해야 합니다. 이러한 숫자는 서로소이고 공약수는 1입니다.

유클리드 알고리즘

이 알고리즘은 고대 그리스 수학자 Euclid의 이름을 따서 명명되었으며, 그의 저서("Beginnings"의 7권 및 10권)에서 처음으로 설명했습니다. Euclid가 이 알고리즘의 작성자가 아닌 것으로 알려져 있습니다. 그럼에도 불구하고 오늘날 사용되는 가장 오래된 알고리즘 중 하나로 간주됩니다.

유클리드의 알고리즘을 사용하면 두 양수의 최대 공약수를 쉽게 계산할 수 있습니다.

GCD(a, b)를 찾기 위해 이 알고리즘은 다음과 같습니다.

a = 0이면 gcd(a, b) = b이고 알고리즘이 중지되기 때문입니다.
만약 b = 0이면 gcd(a, b) = a입니다. 왜냐하면 gcd(a, 0) = a이고 알고리즘이 중지되기 때문입니다.
a를 b로 나누고 나머지(a = b ⋅ q + r)
gcd(a, b) = gcd(b, r)이므로 Euclid의 알고리즘을 사용하여 gcd(b, r)을 찾습니다.

실제 방법의 효과를 확인하기 위해 예를 고려하십시오.

숫자 270과 192의 GCD를 결정해야 합니다.

a = 270, b = 192.
<리>a ≠ 0. <리>b ≠ 0.

a를 b로 나누면 다음과 같이 됩니다.

270 / 192 = 1(나머지는 78)입니다.

결과를 다음과 같이 작성할 수 있습니다. 270 = 192 ⋅ 1 + 78.

다음으로 gcd(270, 192) = gcd(192, 78)이므로 gcd(192, 78)를 계산합니다.

계속 진행하겠습니다.

a = 192, b = 78.
<리>a ≠ 0. <리>b ≠ 0.

a를 b로 나누면 다음과 같이 됩니다.

192 / 78 = 2(나머지는 36)입니다.

다음과 같이 작성할 수 있습니다.

<리>192 = 78 ⋅ 2 + 36.

gcd(192, 78) = gcd(78, 36)이므로 gcd(78, 36)을 계산합니다.

a = 78, b = 36.
<리>a ≠ 0. <리>b ≠ 0.

a를 b로 나누면 다음과 같이 됩니다.

78 / 36 = 2(나머지는 0).

결과를 다음과 같이 작성해 보겠습니다.

<리>78 = 36 ⋅ 2 + 6.

gcd(78, 36) = gcd(36, 6)이므로 gcd(36, 6)을 계산합니다.

a = 36, b = 6.
<리>a ≠ 0. <리>b ≠ 0.

A를 B로 나누면 36 / 6 = 6이 됩니다(나머지는 0).

결과를 다음 형식으로 작성합니다.

<리>36 = 6 ⋅ 6 + 0.

다음으로 gcd(36, 6) = gcd(6, 0)이므로 gcd(6, 0)을 찾습니다.

a = 6, b = 0.
<리>a ≠ 0. <리>b = 0.

그 결과:

gcd(6, 0) = 6.

따라서 다음과 같은 계산 순서가 있습니다.

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

결과적으로 다음과 같은 답을 얻었습니다.

gcd(270, 192) = 6.

위에서 설명한 각 검색 방법에는 장단점이 있습니다. 첫 번째 방법은 더 복잡한 수학 문제를 해결하는 데 사용할 수 있는 두 번째 방법과 달리 비교적 간단한 예를 사용하는 데 적합합니다.

{$ subpageListHide ? ('Show' | translate) : ('Hide' | translate) $}

최대 공약수 계산기