최소 공약수를 구하는 예. 최소공배수 구하기, 방법, LCM 구하는 예

최대 공약수와 최소 공배수는 일반 분수로 쉽게 연산할 수 있는 주요 산술 개념입니다. LCM은 여러 분수의 공통 분모를 찾는 데 가장 자주 사용됩니다.

기본 개념

정수 X의 제수는 X가 나머지 없이 나누어지는 또 다른 정수 Y입니다. 예를 들어, 4의 제수는 2이고 36은 4, 6, 9입니다. 정수 X의 배수는 나머지 없이 X로 나누어 떨어지는 숫자 Y입니다. 예를 들어 3은 15의 배수이고 6은 12의 배수입니다.

모든 숫자 쌍에 대해 공약수와 배수를 찾을 수 있습니다. 예를 들어, 6과 9의 경우 공배수는 18이고 공약수는 3입니다. 분명히 쌍에는 여러 제수와 배수가 있을 수 있으므로 GCD의 가장 큰 약수와 LCM의 가장 작은 배수가 계산에 사용됩니다. .

가장 작은 제수는 의미가 없습니다. 모든 숫자에 대해 항상 1이기 때문입니다. 가장 큰 배수도 의미가 없습니다. 배수의 시퀀스는 무한대가 되는 경향이 있기 때문입니다.

GCD 찾기

최대 공약수를 구하는 방법에는 여러 가지가 있으며 그 중 가장 유명한 방법은 다음과 같습니다.

• 제수의 순차적 열거, 쌍에 대한 공통의 선택 및 가장 큰 것 검색;
• 숫자를 나눌 수 없는 요소로 분해;
• 유클리드 알고리즘;
• 이진 알고리즘.

오늘 교육 기관가장 인기 있는 것은 소인수분해 방법과 유클리드 알고리즘입니다. 후자는 차례로 디오판틴 방정식을 푸는 데 사용됩니다. 방정식을 정수로 해결할 가능성을 확인하려면 GCD를 검색해야 합니다.

NOC 찾기

최소 공배수는 반복적인 열거 또는 나눌 수 없는 요인으로의 인수분해에 의해 정확하게 결정됩니다. 또한 최대 약수가 이미 결정된 경우 LCM을 쉽게 찾을 수 있습니다. 숫자 X와 Y의 경우 LCM과 GCD는 다음 관계로 연결됩니다.

LCM(X,Y) = X × Y / GCM(X,Y).

예를 들어, gcd(15,18) = 3이면 LCM(15,18) = 15 × 18 / 3 = 90입니다. LCM의 가장 분명한 용도는 공통 분모를 찾는 것입니다. 주어진 분수.

공소수

한 쌍의 숫자에 공약수가 없으면 그러한 쌍을 공소수(coprime)라고 합니다. 이러한 쌍에 대한 GCM은 항상 1과 같으며 제수와 배수의 연결을 기반으로 하여 공소수에 대한 GCM은 해당 곱과 같습니다. 예를 들어, 숫자 25와 28은 공약수가 없기 때문에 공소이고 LCM(25, 28) = 700이며, 이는 해당 제품에 해당합니다. 나누어지지 않는 두 수는 항상 공소수입니다.

공약수와 다중 계산기

계산기를 사용하면 선택할 수 있는 임의의 숫자에 대한 GCD 및 LCM을 계산할 수 있습니다. 공약수와 배수를 계산하는 작업은 5, 6 학년의 산술에서 찾을 수 있지만 GCD 및 LCM - 주요 컨셉수학에서 사용되며 정수론, 평면도 및 의사소통 대수학에 사용됩니다.

실생활의 예

분수의 공통 분모

최소공배수는 여러 분수의 공통분모를 구할 때 사용합니다. 산술 문제에서 5개의 분수를 합해야 한다고 가정합니다.

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

분수를 추가하려면 표현식을 공통 분모로 줄여야 하므로 LCM을 찾는 문제가 줄어듭니다. 이렇게하려면 계산기에서 5 개의 숫자를 선택하고 해당 셀에 분모 값을 입력하십시오. 프로그램은 LCM (8, 9, 12, 15, 18) = 360을 계산합니다. 이제 분모에 대한 LCM의 비율로 정의되는 각 분수에 대한 추가 인수를 계산해야 합니다. 따라서 추가 승수는 다음과 같습니다.

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

그 후, 우리는 모든 분수에 해당하는 추가 요소를 곱하고 다음을 얻습니다.

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

이러한 분수를 쉽게 추가하고 159/360 형식의 결과를 얻을 수 있습니다. 분수를 3으로 줄이고 최종 답인 53/120을 봅니다.

선형 디오판틴 방정식의 해

선형 디오판틴 방정식은 ax + by = d 형식의 표현입니다. 비율 d / gcd(a, b)가 정수이면 방정식은 정수로 풀 수 있습니다. 정수 솔루션의 가능성에 대한 몇 가지 방정식을 확인합시다. 먼저 방정식 150x + 8y = 37을 확인합니다. 계산기를 사용하여 gcd(150.8) = 2를 찾습니다. 37/2 = 18.5를 나눕니다. 숫자는 정수가 아니므로 방정식에 정수 근이 없습니다.

방정식 1320x + 1760y = 10120을 확인합시다. 계산기를 사용하여 gcd(1320, 1760) = 440을 구합니다. 10120/440 = 23을 나눕니다. 결과적으로 정수를 얻습니다. 따라서 디오판틴 방정식은 정수 계수로 풀 수 있습니다 .

결론

GCD와 LCM은 정수론에서 중요한 역할을 하며, 개념 자체는 수학의 다양한 영역에서 널리 사용됩니다. 계산기를 사용하여 숫자의 가장 큰 약수와 가장 작은 배수를 계산하십시오.

문제를 해결합시다. 두 가지 유형의 쿠키가 있습니다. 일부는 초콜릿이고 일부는 플레인입니다. 초콜릿 조각은 48개, 단순 조각은 36개입니다. 이 쿠키에서 가능한 한 많은 선물을 만들어야 하며 모두 사용해야 합니다.

먼저, 이 두 숫자 모두 선물의 수로 나누어떨어져야 하므로 이 두 숫자 각각의 약수를 모두 적어 보겠습니다.

우리는 얻는다

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

제수 중에서 첫 번째와 두 번째 숫자가 모두 갖는 공통적인 것을 찾자.

공약수는 1, 2, 3, 4, 6, 12입니다.

모든 것의 최대공약수는 12입니다. 이 수를 36과 48의 최대공약수라고 합니다.

결과에 따라 모든 쿠키에서 12개의 선물을 만들 수 있다는 결론을 내릴 수 있습니다. 그러한 선물 중 하나에는 4개의 초콜릿 쿠키와 3개의 일반 쿠키가 포함됩니다.

최대공약수 구하기

• 가장 위대한 자연수, 두 수와 b가 나머지 없이 나누어지는 수를 이 수의 최대공약수라고 합니다.

때때로 약어 GCD는 항목을 축약하는 데 사용됩니다.

일부 숫자 쌍의 최대 공약수는 1입니다. 이러한 숫자를 공소수.예를 들어 숫자 24와 35입니다. GCD = 1입니다.

최대공약수 구하는 방법

최대공약수를 구하기 위해 이 숫자들의 약수를 모두 쓸 필요는 없습니다.

그렇지 않으면 할 수 있습니다. 먼저 두 숫자를 소인수로 인수분해합니다.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

이제 첫 번째 숫자의 확장에 포함된 요소에서 두 번째 숫자의 확장에 포함되지 않은 모든 요소를 ​​삭제합니다. 우리의 경우 이것은 두 개의 듀스입니다.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

약수 2, 2, 3이 남아 있고 그 곱은 12입니다. 이 숫자는 숫자 48과 36의 최대 공약수가 됩니다.

이 규칙은 3, 4 등의 경우까지 확장될 수 있습니다. 번호.

최대공약수를 구하는 일반적인 방법

• 1. 숫자를 소인수로 분해합니다.
• 2. 이 숫자 중 하나의 확장에 포함된 요소에서 다른 숫자의 확장에 포함되지 않은 요소를 지웁니다.
• 3. 나머지 요소의 곱을 계산합니다.

세 개 이상의 수의 최대공약수를 구하는 것은 두 수의 gcd를 연속적으로 구하는 것으로 축소될 수 있습니다. 우리는 GCD의 속성을 연구할 때 이것을 언급했습니다. 거기에서 우리는 정리를 공식화하고 증명했습니다: 여러 수의 최대 공약수 a 1 , a 2 , … , k숫자와 같습니다 닥, 순차 계산에서 찾을 수 있습니다. GCD(a 1 , a 2)=d 2, GCD(d 2 , a 3)=d 3, GCD(d 3 , a 4)=d 4, …,GCD(d k-1 , k)=d k.

예제의 솔루션을 고려하여 여러 숫자의 GCD를 찾는 과정이 어떻게 보이는지 봅시다.

예시.

네 수의 최대공약수 구하기 78 , 294 , 570 그리고 36 .

해결책.

이 예에서 1 = 78, a2=294, a 3 \u003d 570, a4=36.

먼저 유클리드 알고리즘을 사용하여 최대 공약수를 결정합니다. d2처음 두 숫자 78 그리고 294 . 나눌 때 평등을 얻습니다. 294=78 3+60; 78=60 1+18;60=18 3+6그리고 18=6 3. 이런 식으로, d 2 \u003d GCD (78, 294) \u003d 6.

이제 계산해보자 d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). 유클리드 알고리즘을 다시 사용해보자. 570=6 95, 그 후, d 3 \u003d GCD (6, 570) \u003d 6.

계산이 남았다 d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). 왜냐하면 36 로 나눈 6 , 그 다음에 d 4 \u003d GCD (6, 36) \u003d 6.

따라서 주어진 네 수의 최대공약수는 d4=6, 그건, gcd(78, 294, 570, 36)=6.

대답:

gcd(78, 294, 570, 36)=6.

숫자를 소인수로 분해하면 세 개 이상의 숫자의 GCD를 계산할 수도 있습니다. 이 경우 최대 공약수는 주어진 숫자의 모든 공약수를 곱한 값입니다.

예시.

소인수분해를 사용하여 이전 예제에서 숫자의 GCD를 계산합니다.

해결책.

숫자를 분해해보자 78 , 294 , 570 그리고 36 주요 요인으로, 우리는 78=2 3 13,294=2 3 7 7, 570=2 3 5 19, 36=2 2 3 3. 주어진 4개의 모든 숫자의 공통 소인수는 숫자입니다. 2 그리고 3 . 따라서, GCD(78, 294, 570, 36)=2 3=6.

대답:

gcd(78, 294, 570, 36)=6.

페이지 상단

음수의 gcd 찾기

최대 약수를 찾아야 하는 숫자 중 하나, 여러 개 또는 모두가 음수이면 gcd는 이 숫자 모듈의 최대 공약수와 같습니다. 숫자가 반대이기 때문입니다. ㅏ그리고 -ㅏ나눗셈의 속성을 연구할 때 논의한 동일한 제수를 갖습니다.

예시.

음의 정수의 gcd 찾기 −231 그리고 −140 .

해결책.

숫자의 절대값 −231 같음 231 , 그리고 숫자의 계수 −140 같음 140 , 그리고 gcd(−231, −140)=gcd(231, 140). 유클리드 알고리즘은 다음과 같은 등식을 제공합니다. 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7그리고 42=7 6. 따라서, gcd(231, 140)=7. 그런 다음 음수의 원하는 최대 공약수 −231 그리고 −140 같음 7 .

대답:

GCD(−231,−140)=7.

예시.

세 숫자의 gcd 결정 −585 , 81 그리고 −189 .

해결책.

최대 공약수를 찾을 때 음수는 절대값으로 대체될 수 있습니다. 즉, gcd(−585, 81, −189)=gcd(585, 81, 189). 숫자 확장 585 , 81 그리고 189 소인수는 각각 다음과 같은 형식입니다. 585=3 3 5 13, 81=3 3 3 3그리고 189=3 3 3 7. 이 세 숫자의 공통 소인수는 다음과 같습니다. 3 그리고 3 . 그 다음에 GCD(585, 81, 189)=3 3=9, 그 후, gcd(−585, 81, −189)=9.

대답:

gcd(−585, 81, −189)=9.

35. 다항식의 근. Bezout의 정리. (33세 이상)

36. 다중 루트, 루트의 다중성의 기준.

이 기사는 최대 공약수를 찾는 것과 같은 질문에 전념합니다. 먼저 그것이 무엇인지 설명하고 몇 가지 예를 들어 2, 3 또는 그 이상의 숫자의 최대 공약수의 정의를 소개한 후 이 개념의 일반적인 속성에 대해 논의하고 증명할 것입니다.

Yandex.RTB R-A-339285-1

공약수란?

최대 공약수가 무엇인지 이해하기 위해 먼저 정수에 대한 공약수가 무엇인지 공식화합니다.

배수와 제수에 대한 기사에서 정수에는 항상 여러 제수가 있다고 말했습니다. 여기서 우리는 한 번에 특정 수의 정수, 특히 모두에게 공통적인(동일한) 제수에 관심이 있습니다. 주요 정의를 적어 보겠습니다.

정의 1

여러 정수의 공약수는 지정된 집합에서 각 숫자의 제수가 될 수 있는 숫자입니다.

실시예 1

다음은 이러한 제수의 예입니다. 9 = 3 · 3 및 − 12 = 3 · (− 4)가 참이기 때문에 트리플은 숫자 - 12와 9의 공약수가 됩니다. 숫자 3 및 - 12 에는 1 , - 1 및 - 3 과 같은 다른 공약수가 있습니다. 다른 예를 들어보겠습니다. 4개의 정수 3 , − 11 , − 8 및 19 는 1 과 - 1 이라는 두 개의 공약수를 가집니다.

나눗셈의 속성을 알면 모든 정수를 1과 마이너스 1로 나눌 수 있다고 말할 수 있습니다. 즉, 모든 정수 집합에는 이미 최소 두 개의 공약수가 있습니다.

또한 여러 숫자 b에 대한 공약수가 있으면 동일한 숫자를 반대 숫자, 즉 - b로 나눌 수 있습니다. 원칙적으로 양의 제수만 취할 수 있으며 모든 공약수도 0보다 커집니다. 이 방법을 사용할 수도 있지만 음수를 완전히 무시해서는 안 됩니다.

최대공약수(gcd)는 무엇입니까?

나눗셈의 속성에 따르면 b가 0이 아닌 정수 a의 제수이면 b의 계수는 의 계수보다 클 수 없으므로 0이 아닌 모든 수는 유한한 수의 제수를 갖습니다. . 이것은 여러 정수의 공약수 중 적어도 하나가 0과 다른 공약수의 수도 유한하며 전체 집합에서 항상 가장 많이 선택할 수 있음을 의미합니다. 큰 숫자(이전에 우리는 가장 큰 정수와 가장 작은 정수의 개념에 대해 이미 이야기 했으므로 이 자료를 반복하는 것이 좋습니다.)

추가 추론에서 최대 공약수를 찾아야 하는 숫자 집합 중 적어도 하나는 0과 다르다고 가정합니다. 그것들이 모두 0 과 같으면 제수는 임의의 정수가 될 수 있으며, 그 수가 무한히 많기 때문에 가장 큰 것을 선택할 수 없습니다. 즉, 0과 같은 수의 집합에 대한 최대공약수를 찾는 것은 불가능합니다.

우리는 주요 정의의 공식화로 넘어갑니다.

정의 2

여러 숫자의 최대 공약수는 모든 숫자를 나누는 가장 큰 정수입니다.

서면에서 최대 공약수는 가장 자주 약어 GCD로 표시됩니다. 두 숫자의 경우 gcd (a, b) 로 쓸 수 있습니다.

실시예 2

두 정수에 대한 GCD의 예는 무엇입니까? 예를 들어, 6과 -15의 경우 3이 됩니다. 이것을 입증합시다. 먼저 6의 모든 약수: ± 6, ± 3, ± 1, 그런 다음 15의 모든 약수: ± 15, ± 5, ± 3 및 ± 1을 기록합니다. 그 후, 우리는 일반적인 것을 선택합니다: 이들은 − 3 , − 1 , 1 및 3 입니다. 이 중에서 가장 큰 수를 선택해야 합니다. 이것은 3이 될 것입니다.

세 개 이상의 숫자에 대해 최대 공약수의 정의는 거의 동일합니다.

정의 3

세 개 이상의 숫자의 최대 공약수는 모든 숫자를 동시에 나누는 가장 큰 정수입니다.

숫자 a 1 , a 2 , … , an n 의 제수는 GCD (a 1 , a 2 , … , an n) 로 편리하게 표시됩니다. 제수 값 자체는 GCD (a 1 , a 2 , … , a n) = b 로 작성됩니다.

실시예 3

다음은 여러 정수의 최대공약수의 예입니다: 12 , - 8 , 52 , 16 . 이것은 4와 같을 것이고, 이는 우리가 gcd (12, - 8, 52, 16) = 4라고 쓸 수 있음을 의미합니다.

이 숫자의 모든 약수를 기록한 다음 가장 큰 약수를 선택하여 이 진술의 정확성을 확인할 수 있습니다.

실제로 최대 공약수가 숫자 중 하나와 같은 경우가 종종 있습니다. 이것은 다른 모든 숫자를 주어진 숫자로 나눌 수 있을 때 발생합니다(기사의 첫 번째 단락에서 우리는 이 진술의 증거를 제공했습니다).

실시예 4

따라서 숫자 60, 15 및 -45의 최대 공약수는 15입니다. 15는 60과 -45뿐만 아니라 그 자체로도 나눌 수 있고 이 모든 숫자에 대해 더 큰 약수는 없기 때문입니다.

코프라임 수는 특별한 경우입니다. 최대공약수가 1인 정수입니다.

GCD와 유클리드 알고리즘의 주요 속성

최대공약수에는 몇 가지 특징이 있습니다. 우리는 그것들을 정리의 형태로 공식화하고 각각을 증명합니다.

이러한 속성은 0보다 큰 정수에 대해 공식화되며 양수 제수만 고려합니다.

정의 4

숫자 a 와 b 는 b 와 a 에 대해 gcd 와 같은 최대 공약수를 가집니다. 즉, gcd (a , b) = gcd (b , a) 입니다. 숫자 자리를 변경해도 최종 결과에는 영향을 미치지 않습니다.

이 속성은 GCD의 정의를 따르며 증명이 필요하지 않습니다.

정의 5

숫자 a를 숫자 b로 나눌 수 있으면 이 두 숫자의 공약수 집합은 숫자 b의 약수 집합과 유사합니다. 즉, gcd (a, b) = b입니다.

이 말을 증명합시다.

증거 1

숫자와 b에 공약수가 있으면 둘 중 하나를 그들로 나눌 수 있습니다. 동시에 가 b 의 배수이면 b 의 제수도 , 의 제수가 됩니다. 왜냐하면 나눗셈은 전이성과 같은 속성을 가지고 있기 때문입니다. 따라서 제수 b는 숫자와 b에 대해 공통입니다. 이것은 우리가 b 로 나눌 수 있다면 두 숫자의 모든 제수 집합이 한 숫자 b의 제수 집합과 일치한다는 것을 증명합니다. 그리고 어떤 숫자의 최대 약수도 숫자 자체이기 때문에 숫자와 b의 최대 공약수도 b와 같습니다. gcd(a, b) = b. a = b 이면 gcd (a , b) = gcd (a , a) = gcd (b , b) = a = b , 예를 들어 gcd (132 , 132) = 132 입니다.

이 속성을 사용하여 두 숫자 중 하나를 다른 숫자로 나눌 수 있는 경우 두 숫자의 최대 공약수를 찾을 수 있습니다. 이러한 제수는 두 번째 숫자를 나눌 수 있는 이 두 숫자 중 하나와 같습니다. 예를 들어, gcd (8, 24) = 8입니다. 24는 8의 배수이기 때문입니다.

정의 6 증거 2

이 속성을 증명해 봅시다. 우리는 처음에 a = b q + c 라는 평등을 가지고 있고, a와 b의 공약수는 c도 나눌 것입니다. 이는 해당 나눌 수 있는 속성으로 설명됩니다. 따라서 b와 c의 공약수는 a를 나눕니다. 이것은 공약수와 b의 집합이 가장 큰 것을 포함하여 약수 b와 c의 집합과 일치한다는 것을 의미하며, 이는 gcd (a, b) = gcd (b, c)가 참임을 의미합니다.

정의 7

다음 속성을 유클리드 알고리즘이라고 합니다. 이를 통해 두 숫자의 최대 공약수를 계산하고 GCD의 다른 속성을 증명할 수 있습니다.

속성을 공식화하기 전에 나머지로 나눗셈에 관한 기사에서 증명한 정리를 반복하는 것이 좋습니다. 그것에 따르면, 나눌 수 있는 수 a는 bq + r로 나타낼 수 있으며, 여기서 b는 제수, q는 일부 정수(불완전 몫이라고도 함), r은 0 ≤ r ≤ 조건을 만족하는 나머지입니다. 비.

다음 등이 참인 0보다 큰 두 개의 정수가 있다고 가정해 보겠습니다.

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

이러한 평등은 r k + 1 이 0 이 될 때 끝납니다. 시퀀스 b > r 1 > r 2 > r 3 , … 은 유한한 수만 포함할 수 있는 일련의 감소하는 정수이기 때문에 이것은 확실히 일어날 것입니다. 따라서 r k 는 a 와 b 의 최대 공약수, 즉 r k = gcd (a , b) 입니다.

먼저, rk가 와 b의 공약수임을 증명하고, 그 후 rk가 단순한 제수가 아니라 주어진 두 수의 최대공약수임을 증명해야 합니다.

위의 평등 목록을 아래에서 위로 살펴보겠습니다. 마지막 평등에 따르면,
r k − 1 은 r k 로 나눌 수 있습니다. 이 사실과 최대공약수의 이전에 증명된 속성에 기초하여 r k − 2 는 r k 로 나눌 수 있다고 주장할 수 있습니다.
r k − 1 은 r k 로 나눌 수 있고 r k 는 r k 로 나눌 수 있습니다.

아래에서 세 번째 등식을 통해 r k − 3 을 r k 등으로 나눌 수 있다는 결론을 내릴 수 있습니다. 아래에서 두 번째는 b 가 r k 로 나눌 수 있다는 것이고 첫 번째는 a 가 r k 로 나눌 수 있다는 것입니다. 이 모든 것에서 우리는 r k 가 및 b 의 공약수라는 결론을 내립니다.

이제 r k = gcd (a , b) 임을 증명해 봅시다. 내가 무엇을해야 하나? a 와 b 의 공약수는 r k 를 나눕니다. r 0 으로 표시합시다.

동일한 평등 목록을 위에서 아래로 살펴보겠습니다. 이전 속성을 기반으로 r 1 은 r 0 으로 나눌 수 있다는 결론을 내릴 수 있습니다. 즉, 두 번째 등식에 따르면 r 2 는 r 0 으로 나눌 수 있습니다. 우리는 모든 등식을 살펴보고 마지막 것에서 r k 가 r 0 으로 나눌 수 있다는 결론을 내립니다. 따라서 r k = gcd (a , b) 입니다.

이 속성을 고려하여 a 및 b의 공약수 집합이 이 숫자의 gcd 약수 집합과 유사하다는 결론을 내립니다. 유클리드 알고리즘의 결과인 이 진술을 통해 주어진 두 수의 모든 공약수를 계산할 수 있습니다.

다른 속성으로 넘어갑시다.

정의 8

a와 b가 0이 아닌 정수이면 gcd (a , b) = a u 0 + b v 0이 유효할 두 개의 다른 정수 u 0 및 v 0이 있어야 합니다.

속성 설명에 주어진 등식은 및 b 의 최대 공약수를 선형으로 표현한 것입니다. 이를 Bezout 비율이라고 하며 u 0 과 v 0 의 숫자를 Bezout 계수라고 합니다.

증거 3

이 속성을 증명합시다. Euclid 알고리즘에 따라 등식 시퀀스를 기록합니다.

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

첫 번째 등식은 r 1 = a − b · q 1 임을 알려줍니다. 1 = s 1 및 − q 1 = t 1 을 나타내고 이 등식을 r 1 = s 1 · a + t 1 · b 로 다시 씁니다. 여기서 숫자 s 1 과 t 1 은 정수가 됩니다. 두 번째 등식을 통해 r 2 = b − r 1 q 2 = b − (s 1 a + t 1 b) q 2 = − s 1 q 2 a + (1 − t 1 q 2) b 라고 결론을 내릴 수 있습니다. − s 1 q 2 = s 2 및 1 − t 1 q 2 = t 2 를 나타내고 등식을 r 2 = s 2 a + t 2 b 로 다시 작성합니다. 여기서 s 2 및 t 2 역시 정수가 됩니다. 정수의 합과 곱과 차이도 정수이기 때문입니다. 정확히 같은 방식으로 세 번째 등식 r 3 = s 3 · a + t 3 · b , 다음 r 4 = s 4 · a + t 4 · b 등으로부터 얻습니다. 마지막으로 정수 s k 와 t k 에 대해 r k = s k a + t k b 라는 결론을 내립니다. rk \u003d GCD (a, b) 이므로 sk \u003d u 0 및 tk \u003d v 0으로 표시합니다. 결과적으로 GCD의 선형 표현을 필요한 형식으로 얻을 수 있습니다. GCD (a, b) \u003d au 0 + bv 0.

정의 9

gcd(m a, m b) = m gcd(a, b) 자연 가치중 .

증거 4

이 속성은 다음과 같이 정당화될 수 있습니다. Euclid 알고리즘에서 각 평등의 양변에 m을 곱하면 gcd (m a , m b) = m r k 이고 r k 는 gcd (a , b) 입니다. 따라서 gcd (m a, m b) = m gcd (a, b) 입니다. 인수분해 방법으로 GCD를 찾을 때 사용되는 최대공약수의 이 속성입니다.

정의 10

숫자 a와 b의 공약수 p 가 있으면 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)는 공소수입니다.

a = p (a: p) 및 b = p (b: p) 이므로 이전 속성을 기반으로 gcd (a , b) = gcd (p (a: p) 형식의 등식을 만들 수 있습니다. p(b:p)) = p GCD(a:p, b:p) , 그 중 증거가 있을 것 주어진 재산. 우리는 다음을 제공할 때 이 주장을 사용합니다. 공통 분수환원 불가능한 형태로

정의 11

최대공약수 a 1 , a 2 , ... , ak 은 수 dk 가 됩니다. 이는 gcd (a 1 , a 2) = d 2 , gcd (d 2 , a 3) = d를 연속적으로 계산하여 찾을 수 있습니다. 3 , gcd (d 3 , a 4) = d 4 , … , gcd (dk - 1 , ak) = dk .

이 속성은 세 개 이상의 숫자의 최대 공약수를 찾는 데 유용합니다. 이를 통해 이 작업을 두 개의 숫자가 있는 작업으로 줄일 수 있습니다. 그 기초는 유클리드 알고리즘의 결과입니다. 공약수 a 1 , a 2 및 a 3 의 집합이 집합 d 2 및 a 3 과 일치하면 제수 d 3 과도 일치합니다. 숫자 a 1 , a 2 , a 3 및 a 4 의 제수는 d 3 의 제수와 일치합니다. 즉, d 4 의 제수도 일치하는 식입니다. 결국, 우리는 숫자 a 1 , a 2 , … , ak 의 공약수가 제수 dk 와 일치하고 숫자 자체가 숫자 dk 의 최대 약수가 될 것이기 때문에 gcd (a 1 , a 2 , … , ak) = dk .

이것이 우리가 최대공약수의 속성에 대해 이야기하고 싶은 전부입니다.

텍스트에서 실수를 발견하면 강조 표시하고 Ctrl+Enter를 누르십시오.

이 기사는 최대공약수(gcd) 구하기두 개 이상의 숫자. 먼저 유클리드 알고리즘을 고려하면 두 숫자의 GCD를 찾을 수 있습니다. 그 다음에는 공통 소인수의 곱으로 숫자의 GCD를 계산할 수 있는 방법에 대해 설명합니다. 다음으로 세 개 이상의 숫자의 최대공약수를 구하는 방법과 음수의 GCD를 계산하는 예를 보여드리겠습니다.

페이지 탐색.

GCD를 찾는 유클리드 알고리즘

우리가 맨 처음부터 소수의 표로 돌아갔다면, 우리는 661과 113이 소수라는 것을 알았을 것이고, 여기서 우리는 그들의 최대 공약수가 1이라고 즉시 말할 수 있습니다.

대답:

gcd(661, 113)=1 .

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

GCD를 찾는 다른 방법을 고려하십시오. 최대공약수는 숫자를 소인수로 분해하여 구할 수 있습니다. 규칙을 공식화합시다. 두 개의 양의 정수 및 b의 gcd는 및 b를 소인수로 인수분해하는 모든 공통 소인수의 곱과 같습니다..

GCD를 찾는 규칙을 설명하기 위해 예를 들어 보겠습니다. 숫자 220과 600을 소인수로 확장하면 220=2 2 5 11 및 600=2 2 3 5 5 형식이 됩니다. 숫자 220 및 600 의 확장과 관련된 일반적인 소인수는 2 , 2 및 5 입니다. 따라서 gcd(220, 600)=2 2 5=20 입니다.

따라서 숫자와 b를 소인수로 분해하고 모든 공약수의 곱을 구하면 숫자와 b의 최대 공약수가 됩니다.

발표된 규칙에 따라 GCD를 찾는 예를 고려하십시오.

예시.

72와 96의 최대공약수를 구하세요.

해결책.

숫자 72와 96을 인수분해해 보겠습니다.

즉, 72=2 2 2 3 3 및 96=2 2 2 2 3 입니다. 일반적인 소인수는 2 , 2 , 2 및 3 입니다. 따라서 gcd(72, 96)=2 2 2 3=24 입니다.

대답:

gcd(72, 96)=24 .

이 섹션의 결론에서 우리는 gcd를 찾기 위한 위 규칙의 유효성이 다음과 같은 최대 공약수의 속성에서 비롯된다는 점에 주목합니다. GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), 여기서 m은 양의 정수입니다.

세 개 이상의 숫자의 GCD 찾기

세 개 이상의 수의 최대공약수를 구하는 것은 두 수의 gcd를 연속적으로 구하는 것으로 축소될 수 있습니다. 우리는 GCD의 속성을 연구할 때 이것을 언급했습니다. 거기에서 우리는 정리를 공식화하고 증명했습니다. 여러 숫자의 최대 공약수 a 1 , a 2 , … , gcd(d 2 , a 3) =d 3 , GCD(d 3 , a 4)=d 4 , … , GCD(d k-1 , ak)=dk .

예제의 솔루션을 고려하여 여러 숫자의 GCD를 찾는 과정이 어떻게 보이는지 봅시다.

예시.

4개의 숫자 78, 294, 570, 36의 최대공약수를 구하세요.

해결책.

이 예에서 a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 입니다.

먼저 유클리드 알고리즘을 사용하여 처음 두 숫자 78과 294의 최대 공약수 d 2 를 결정합니다. 나눌 때 평등을 얻습니다. 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 및 18=6 3 . 따라서 d 2 =GCD(78, 294)=6 입니다.

이제 계산해보자 d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). 다시 Euclid 알고리즘을 적용합니다. 570=6·95 , 따라서 d 3 =gcd(6, 570)=6 입니다.

계산이 남았다 d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). 36은 6으로 나눌 수 있으므로 d 4 \u003d GCD (6, 36) \u003d 6입니다.

따라서 주어진 네 수의 최대 공약수는 d 4 =6 , 즉 gcd(78, 294, 570, 36)=6 입니다.

대답:

gcd(78, 294, 570, 36)=6 .

숫자를 소인수로 분해하면 세 개 이상의 숫자의 GCD를 계산할 수도 있습니다. 이 경우 최대 공약수는 주어진 숫자의 모든 공약수를 곱한 값입니다.

예시.

소인수분해를 사용하여 이전 예제에서 숫자의 GCD를 계산합니다.

해결책.

숫자 78 , 294 , 570 및 36 을 소인수로 분해하면 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 . 주어진 4개의 숫자의 공통 소인수는 숫자 2와 3입니다. 따라서, GCD(78, 294, 570, 36)=2 3=6.