최대 공약수 계산기

웹사이트에 추가 메타정보

다른 도구들

최대 공약수 계산기

최대 공약수 계산기

최대 공약수(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.

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