Статии

1.5: Най-големият общ делител - математика


В този раздел дефинираме най-големия общ делител (gcd) на две цели числа и обсъждаме неговите свойства. Ние също така доказваме, че най-големият общ делител на две цели числа е линейна комбинация от тези цели числа.

Две цели числа (a ) и (b ), а не двете (0 ), могат да имат само крайно много делители (вж. Упражнение [exer: sizeofdivisors]) и по този начин могат да имат само крайно много делители. В този раздел се интересуваме от най-големия от тези общи делители.

Като се има предвид (a, b in ZZ ), а не и нула, а най-големият общ делител е най-голямото цяло число, което разделя както (a ), така и (b ) и се записва ( gcd (a, b) ) (или понякога просто ((a, b) )).

Когато улесни формулата, ще напишем ( gcd (0,0) = 0 ).

[например: gcda] Най-големият общ делител на 24 и 18 е 6. С други думи ( gcd (24,18) = 6 ).

(a, b в ZZ ) се казва относително първокласен ако ( gcd (a, b) = 1 ).

[например: gcdb] Най-големият общ делител на 9 и 16 е 1, следователно те са относително прости.

Имайте предвид, че всяко цяло число има положителни и отрицателни делители. Ако (a ) е положителен делител на (m ), тогава (- a ) също е делител на (m ). Следователно от нашата дефиниция за най-големия общ делител можем да видим, че ( gcd (a, b) = gcd (| a |, | b |) ).

Можем да използваме gcd на две цели числа, за да направим относително прости числа:

[thm: dividebygcd] Ако (a, b in ZZ ) имат ( gcd (a, b) = d ), тогава ( gcd (a / d, b / d) = 1 ).

Поправете (a, b in ZZ ). Ще покажем, че (a / d ) и (b / d ) нямат общи положителни делители, различни от (1 ). Нека (k in NN ) е делител на (a / d ) и (b / d ), така че ( съществува m, n in NN ), така че [a / d = km hspace {0,3 cm} mbox {и} b / d = kn ] По този начин получаваме, че [a = kmd hspace {0,3 cm} mbox {и} b = knd. ] Следователно (kd ) е общ делител както на (a ), така и на (b ). Също така, (kd geq d ). (D ) обаче е най-големият общ делител на (a ) и (b ). В резултат получаваме това (k = 1 ).

Следващата теорема показва, че най-големият общ делител на две цели числа не се променя, когато добавим кратно на едно от двете цели числа към другото.

Нека (a, b, c in ZZ ). Тогава ( gcd (a, b) = gcd (a + cb, b) ).

Ще покажем, че всеки делител на (a ) и (b ) също е делител на (a + cb ) и (b ) и обратно. Следователно те имат абсолютно еднакви делители. Така получаваме, че най-големият общ делител на (a ) и (b ) ще бъде и най-големият общ делител на (a + cb ) и (b ). Нека (k ) е общ делител на (a ) и (b ). По теорема [thm: делимостсъединява], (k mid (a + cb) ) и следователно (k ) е делител на (a + cb ). Сега приемете, че (l ) е общ делител на (a + cb ) и (b ). Също така по теорема [thm: делимосткомкомбини] имаме, [l mid ((a + cb) -cb) = a.]] В резултат на това (l ) е общ делител на (a ) и (b ) и резултатът следва.

[например: gcdc] Забележете, че ( gcd (4,14) = gcd (4,14-3 cdot 4) = gcd (4,2) = 2 ).

Сега представяме теорема, която доказва, че най-големият общ делител на две цели числа може да бъде записан като линейна комбинация от двете цели числа.

[thm: gcdislincomb] Нека (a, b in ZZ ) и двете не са нула. Тогава ( gcd (a, b) ) е най-малкото естествено число, което е с формата (d = ma + nb ) за някои (m, n in ZZ ).

Да приемем, без загуба на общ характер, че (a, b in NN ) са положителни цели числа. Помислете за набор [S = {d in NN mid d = ma + nb text { за някои } m, n in ZZ } . ] (S ) не е празно, тъй като (a = 1 cdot a + 0 cdot b ) и (b = 0 cdot a + 1 cdot b ) са и в (S ). Нека (d in NN ) е най-малкият елемент на (S ), чието съществуване е гарантирано от принципа на доброто подреждане. Забележете (d = ma + nb ) за някои (m, n in ZZ ), тъй като (d в S ). Все още трябва да докажем, че (d ) разделя и (a ), и (b ) и че е най-големият такъв общ делител.

Чрез алгоритъма за разделяне, ( съществува q, r в ZZ ), така че [a = qd + r, 0 leq r

Същият аргумент ще покаже, че (d mid b ).

Сега забележете, че ако има делител (c ), който разделя и (a ), и (b ). Тогава (c ) разделя всяка линейна комбинация от (a ) и (b ) по теорема [thm: делимостcomcombs]. Следователно (c mid d ). Това доказва, че всеки общ делител на (a ) и (b ) разделя (d ). Следователно (c leq d ) и (d ) е най-големият общ делител.

Има просто приложение на това, което ще бъде много полезно в бъдеще:

[cor: intlincombrelprime] Ако (a, b in ZZ ) са относително прости, тогава ( съществува m, n в ZZ ), така че (ma + nb = 1 ).

За някои (n in NN ), нека (a_1, a_2, dots, a_n in ZZ ) не са всички (0 ). The най-големият общ делител от тези цели числа е най-голямото цяло число, което разделя всички и се обозначава ( gcd (a_1, dots, a_n) ).

За някои (n in NN ), (a_1, a_2, dots, a_n in ZZ ) се казва, че са взаимно относително първостепенни ако ( gcd (a_1, a_2, точки, a_n) = 1 ).

[например: mutrelprime] Целите числа (3, 6, 7 ) са взаимно относително прости, тъй като ((3,6,7) = 1 ), въпреки че ((3,6) = 3 ).

За някои (n in NN ) се извикват (a_1, a_2, dots, a_n in ZZ ) по двойки относително първостепенни ако ( forall i, j in NN ) такива, че (i le n ), (j le n ) и (i neq j ), имаме ( gcd (a_i, a_j) = 1 ).

[например: pairwiserelprime] Целите числа (3,14,25 ) са двойно относително прости. Забележете също, че тези цели числа са относително прости.

За (n in NN ) и (a_1, dots, a_n in ZZ ), ако (a_1, a_2, dots, a_n ) са двойно относително прости, тогава те са взаимно относително прости.

Упражнения за §5

Намерете най-големия общ делител на 15 и 35.

Намерете най-големия общ делител на 100 и 104.

Намерете най-големия общ делител на -30 и 95.

Нека (m in NN ). Намерете най-големия общ делител на (m ) и (m + 1 ).

Нека (m in NN ), намери най-големия общ делител на (m ) и (m + 2 ).

Покажете, че ако (m, n in ZZ ) имат ( gcd (m, n) = 1 ), тогава ( gcd (m + n, mn) = 1 ) или (2 ).

Покажете, че ако (m in NN ), тогава (3m + 2 ) и (5m + 3 ) са относително прости.

Покажете, че ако (a, b in ZZ ) са относително прости, тогава ( gcd (a + 2b, 2a + b) = 1 ) или (3 ).

Покажете, че ако (a_1, a_2, dots, a_n in ZZ ) не са всички (0 ) и (c in NN ), тогава ( gcd (ca_1, ca_2, dots , ca_n) = c cdot gcd (a_1, a_2, dots, a_n). )


Най-големият общ делител (GCD) - математически задачи


    Класната стая е дълга 9 метра. Ширината на класната стая е по-малка и може да се премине с еднакво дълги стъпки от 55 CM или 70 CM. Определете ширината на класната стая.
    Земята, която е с размери 220 m и 308 m, собственикът иска да раздели на еднакво големи квадратни парцели с възможно най-голяма площ. Колко дълго ще бъде едната страна на сюжета?
    Градинарската колония с размери 180 m и 300 m трябва да бъде напълно разделена на еднакво големи квадратни площи с възможно най-голяма площ. Изчислете колко такива квадратни площи могат да бъдат получени и определете дължината на страната на квадрата.
    В двете трапезарии в сградата за отдих има еднакво подредени столове около масите. Максимум 78 души могат да вечерят в първата трапезария и 54 души във втората. Колко стола могат да бъдат около една маса?
    От две пръчки с дължина 240 см и 210 см е необходимо да се изрежат възможно най-дългите колчета за цветя, така че да не останат остатъци. Колко колчета ще бъде?
    Дървеният блок е с размери 12 см, 24 см и 30 см. Петър иска да го нареже на няколко еднакви кубчета. Поне колко кубчета може да получи?
    От най-малкия брой еднакви кубчета, чиято дължина на ръба се изразява с естествено число, можем ли да изградим блок с размери 12dm x 16dm x 20dm?
    Колко от най-големите квадратни листове водопроводчикът отряза пчелната пита от 16 dm и 96 dm?
    Детският дом получи подарък на Николас от 54 портокала, 81 шоколадови фигурки и 135 ябълки. Всяко дете получи един и същ подарък и нищо не остана. а) Колко пакета могат да бъдат приготвени? б) какво откриха децата в пакета?
    Намерете коефициент преди скобата - най-големият делител 51 a + 34 b + 68 121y-99z-33
    В 6 часа сутринта три автобусни линии тръгват от гарата. Първият ред има интервал от 24 минути. Вторият ред има интервал от 15 минути. Третата линия се движи на равни интервали от повече от 1 минута. Третият ред работи едновременно с t
    Намерете всички общи делители на числа 30 и 45.
    Каква е най-малката дължина на низ, която можем да нарежем на 18 равни части и дори 27 равни части (в дециметри)?
    Напишете седем 4-цифрени числа, които се делят на 3 и в същото време на 4.
    Билетите за шоуто струват някакво цяло число, по-голямо от 1. Също така, сумата от цената на билетите за деца и възрастни, както и техния продукт, е степента на простото число. Намерете всички възможни цени на билетите.
    Роман тръгна по моста. Когато чу свирката, той се обърна и видя, че Камил тича в началото на моста. Ако отиде при него, ще се срещнат в средата на моста. Роман обаче се втурна и затова не искаше да губи време, връщайки се на 150 метра.
    За завъртане на по-малка предавка ще се използва голяма предавка. Голямата предавка ще направи 75 оборота в минута. По-малката предавка трябва да прави 384 оборота в минута. Намерете най-малкия брой зъби, които всяка предавка може да има. [Съвет: Използвайте GCF или LCM. ]
    Там са дадени числото C = 281, D = 201. Намерете най-голямото естествено число S, така че C: S, D: S да са с остатъка от 1,
    Разделете правоъгълна хартия с размери 220 мм и 308 мм на квадрати със същия размер, така че да са възможно най-големи. Посочете дължината на страната на квадрата.
    По пътя растат четири тополи. Разстоянията между тях са 35 m, 14 m и 91 m. Най-малко колко тополи трябва да бъдат изпуснати, за да се създаде еднакво разстояние между дърветата? Колко метра ще бъде?

Практика

Изброяване на факторите

Въпроси

  1. Намерете най-големия общ коефициент 18 и 27.
  2. Намерете най-големия общ коефициент 25, 75 и 125.
  3. Намерете най-големия общ коефициент от 19 и 32.

Решения

  1. Положителните фактори на 18 са 1, 2, 3, 6, 9 и 18.
    Положителните фактори на 27 са 1, 3, 9 и 27.
    Най-големият брой, който се появява и в двата списъка, е 9, така че това е най-големият общ фактор.
  2. Положителните фактори на 25 са 1, 5 и 25.
    Положителните фактори на 75 са 1, 3, 5, 25 и 75.
    Положителните фактори на 125 са 1, 5, 25 и 125.
    Най-големият брой и в трите списъка е 25, така че това е най-големият общ фактор.
  3. Положителните фактори на 19 са 1 и 19.
    Положителните фактори на 32 са 1, 2, 4, 8, 16 и 32.
    Най-голямото и единствено число, което се появява и в двата списъка, е 1, така че това е най-големият общ фактор. Следователно 19 и 32 са съвместни.

Използване на Prime Factorization

Въпроси

  1. Намерете най-големия общ коефициент от 1272 и 294.
  2. Намерете най-големия общ коефициент 900, 360 и 729.
  3. Намерете най-големия общ коефициент от 72, 144, 258 и 824.

Решения

  1. Основната факторизация на 1272 е 2x2x2x3x53.
    Основната факторизация на 294 е 2x3x7x7.
    И 1272, и 294 съдържат едно 2 и едно 3, така че най-големият общ фактор е 2 & # 2153 = 6.
  2. Основната факторизация на 900 е 2x2x3x3x5x5.
    Основната факторизация на 360 е 2x2x2x3x3x5.
    Основната факторизация на 729 е 3x3x3x3x3x3.
    И трите факторизирани форми включват две три, така че най-големият общ фактор е 3 & # 2153 = 9.
  3. Основната факторизация на 72 е 2x2x2x3x3.
    Основната факторизация на 144 е 2x2x2x2x3x3.
    Основната факторизация на 258 е 2x3x43.
    Основната факторизация на 824 е 2x2x2x103.

В този случай единственото число, което се появява и във всички четири факторизирани форми, е 2, което е най-големият общ фактор.


Пулверизаторът

Ще извлечем много километри от следния ключов факт:

Най-големият общ делител на (a ) и (b ) е линейна комбинация от (a ) и (b ). Това е,

за някои цели числа (s ) и (t ).

Вече знаем от лема 8.1.2.2, че всяка линейна комбинация от (a ) и (b ) се дели на всеки общ фактор на (a ) и (b ), така че със сигурност се дели на най-големият от тези общи делители. Тъй като всяко константно кратно на линейна комбинация е и линейна комбинация, теорема 8.2.2 предполага, че всяко кратно на gcd е линейна комбинация, което дава:

Следствие 8.2.3. Цялото число е линейна комбинация от (a ) и (b ), ако е кратно на ( text(a, b) ).

Ние & rsquoll доказваме теорема 8.2.2 директно, като обясняваме как да намерим (s ) и (t ). С тази работа се занимава математически инструмент, датиращ от Индия от шести век, където е наречен куттак, което означава & ldquoПулверизаторът. & rdquo Днес Пулверизаторът е по-известен като & ldquothe разширен евклидов gcd алгоритъм, & rdquo, тъй като е толкова близо до алгоритъма Euclid & rsquos.

Например, следвайки алгоритъма Euclid & rsquos, можем да изчислим gcd от 259 и 70, както следва:

Pulverizer преминава през същите стъпки, но изисква допълнително счетоводство по пътя: докато изчисляваме ( text(a, b) ), ние проследяваме как да запишем всеки от остатъците (49, 21 и 7, в примера) като линейна комбинация от (a ) и (b ). Това си струва, защото нашата цел е да напишем последния ненулев остатък, който е GCD, като такава линейна комбинация. За нашия пример ето това допълнително счетоводство:

Започнахме с инициализиране на две променливи, (x = a ) и (y = b ). В първите две колони по-горе изпълнихме алгоритъма Euclid & rsquos. На всяка стъпка изчислихме ( text(x, y) ), което е равно на (x - text(x, y) cdot y ). След това в тази линейна комбинация от (x ) и (y ) заменихме (x ) и (y ) с еквивалентни линейни комбинации от (a ) и (b ), които вече бяхме изчислили. След опростяването ни остана линейна комбинация от (a ) и (b ), равна на ( text(x, y) ), по желание. Крайното решение е в кутия.

Това трябва да стане доста ясно как и защо пулверизаторът работи. Ако имате съмнения, може да ви помогне да работите чрез Задача 8.13, където Пулверизаторът се формализира като автомат на състоянието и след това се проверява с помощта на инвариант, който е продължение на този, използван за алгоритъма Euclid & rsquos.

Тъй като пулверизаторът изисква само малко повече изчисления от алгоритъма Euclid & rsquos, можете много бързо да & ldquopulverize & rdquo много големи числа, като използвате този алгоритъм. Както скоро ще видим, неговата скорост прави Pulverizer много полезен инструмент в областта на криптографията.

Сега можем да преизчислим лема на кана за вода 8.1.5 по отношение на най-големия общ делител:

Следствие 8.2.4. Да предположим, че имаме кани за вода с капацитет (a ) и (b ). Тогава количеството вода във всяка кана винаги е кратно на ( text(a, b) ).

Например, няма начин да се оформят 4 галона, като се използват 3- и 6-галонови кани, защото 4 не е кратно на ( text(3, 6) = 3).


Алгоритъмът на Евклид за най-големия общ делител

Според алгоритъма на Евклид за най-големия общ делител, GCD на две положителни цели числа (a, b) може да се изчисли като:

  • Ако a = 0, тогава GCD (a, b) = b като GCD (0, b) = b.
  • Ако b = 0, тогава GCD (a, b) = a като GCD (a, 0) = a.
  • Ако и a ≠ 0, и b ≠ 0, ние пишем „a“ под формата на остатъчен коефициент (a = b × q + r), където q е коефициентът, а r е остатъкът, а a & gtb.
  • Намерете GCD (b, r) като GCD (b, r) = GCD (a, b)
  • Повтаряме този процес, докато получим остатъка като 0.

Пример: Намерете GCD от 12 и 10, използвайки алгоритъма на Евклид.
Решение: GCD от 12 и 10 може да бъде намерен, като използвате следните стъпки:
a = 12 и b = 10
a ≠ 0 и b ≠ 0
Във форма на остатъчен коефициент можем да напишем 12 = 10 × 1 + 2
По този начин трябва да се намери GCD (10, 2), тъй като GCD (12, 10) = GCD (10, 2)

Сега a = 10 и b = 2
a ≠ 0 и b ≠ 0
Във форма на остатъчен коефициент можем да напишем 10 = 2 × 5 + 0
По този начин трябва да се намери GCD (2,0), тъй като GCD (10, 2) = GCD (2, 0)

Сега a = 2 и b = 0
a ≠ 0 и b = 0
По този начин GCD (2,0) = 2

GCD (12, 10) = GCD (10, 2) = GCD (2, 0) = 2

По този начин GCD от 12 и 10 е 2.

Алгоритъмът на Евклид е много полезен за намиране на GCD с по-големи числа, тъй като в това можем лесно да разделим числата на по-малки числа, за да намерим най-големия общ делител.

Теми, свързани с най-големия общ делител

Вижте тези интересни статии, за да научите повече за най-големия общ делител (GCD) и свързаните с него теми.


Най-големият общ калкулатор на делители

GCD калкулаторът ви позволява бързо да намерите най-големия общ делител на набор от числа. Можете да въведете между две и десет ненулеви цели числа между -2147483648 и 2147483647. Числата трябва да бъдат разделени със запетаи, интервали или раздели или могат да бъдат въведени на отделни редове.

Натиснете бутона „Изчисли GCD“, за да започнете изчислението, или „Нулиране“, за да изпразните формуляра и да започнете отново.

Както за много други инструменти на този уебсайт, вашият браузър трябва да бъде конфигуриран, за да позволи на javascript за програмата да функционира.

Кой е най-големият общ делител?

Най-големият общ делител (известен също като най-големият общ коефициент, най-големият общ делител или най-големият общ коефициент) на набор от числа е най-голямото положително цяло число, което разделя всички числа в множеството без остатък. Това е най-голямото кратно от всички числа в набора.

GCD най-често се изчислява за две числа, когато се използва за намаляване на фракциите до най-ниските им членове. Когато най-големият общ делител на две числа е 1, се казва, че двете числа са coprime или относително първокласен.

Как се изчислява най-големият общ делител?

Този калкулатор използва Алгоритъм на Евклид. За да научите повече за алгоритъма на Евклид или GCD, вижте тази статия в Уикипедия.

GCD може също да се изчисли, като се използва най-рядкото кратно, като се използва тази формула:


Едно от най-полезните неща е, когато искаме да опростим една дроб:

Пример: Как можем да опростим 1230?

По-рано открихме, че общите фактори на 12 и 30 са 1, 2, 3 и 6, и така на Най-големият общ фактор е 6.

Така че най-големият число можем да разделим и 12, и 30 точно на е 6, като този:

÷ 6
1230 = 25
÷ 6

Най-големият общ фактор на 12 и 30 е 6.

И така 1230 може да бъде опростено до 25


Първо ще намерим коефициента на прости числа на 1 и 5. След това ще изчислим коефициентите 1 и 5 и ще намерим най-големия общ коефициент.

Стъпка 2: Основно разделяне на факторизация на 5

Първостепенните фактори на 5 са ​​5. Първо факторизиране на 5 в експоненциална форма е:

Стъпка 3: Фактори на 1

Списък на положителните целочислени фактори на 1, който разделя 1 без остатък.

Стъпка 4: Фактори на 5

Списък на положителните цели числа от 5, който разделя 1 без остатък.

Последна стъпка: Най-големият общ коефициент

Намерихме факторите и коефициента на прости числа на 1 и 5. Най-големият общ коефициент е числото GCF номер.
Така че най-големият общ фактор 1 и 5 е 1.


Връзка с най-малко често срещаното кратно

Продуктът на най-големия общ делител и най-малкото общо кратно на две числа е равен на произведението на двете числа. По този начин, един от най-лесните (и най-систематични) начини за намиране на най-малкото общо кратно е да се изчисли най-големият общ делител и след това да се раздели произведението на числата на тази стойност. Тази връзка е очевидна, когато се използва методът на първостепенно факторизиране за изчисляване на най-големия общ коефициент и най-малкото общо кратно (използвайки първостепенно факторизиране, делителите с най-големи степени се умножават заедно), тъй като всички главни делители се използват или в GCF или LCM.


Работни листове с най-голям общ фактор (GCF)

Голяма колекция от работни листове за GCF е изготвена щателно за ученици от 5 до 8 клас. GCF е известен още като „най-общ делител“ (GCD), „най-общ коефициент“ (HCF), „най-обща мярка“ (GCM) или „най-висок общ делител“ (HCD). Изтеглете и отпечатайте тези работни листове на GCF, за да намерите GCF на две числа, три числа и повече. Опитайте някои от тези материали безплатно!

Избройте факторите за всяка двойка числа. След това сравнете, за да определите GCF на двете числа. Печатните работни листове са категоризирани на три нива въз основа на диапазона от числа.

Използвайте основния метод за факторизиране, за да намерите GCF за всяка двойка числа. Тази партида pdfs на многостепенни работни листове съдържа общо 150 проблема за учениците от 5 и 6 клас. Използвайте клавиша за отговор, за да потвърдите вашите решения.

Запишете факторите за всяка двойка числа в диаграмата на Вен. След това избройте често срещаните фактори в пресечната точка. Най-големият фактор, изброен в припокриващия се регион, е GCF. Този комплект включва числа до 25.

Освежете своя клас по математика, като използвате диаграми на Вен, за да намерите GCF на две числа. С участието на числа до 99, тази компилация изисква от обучаемите да изброят факторите, да поставят общите фактори в припокриващия се регион и да намерят GCF.

Намерете GCF за числителя и знаменателя на дадената фракция в този набор от работни листове за печат. След това намалете фракцията до най-ниския й член чрез разделяне на числителя и знаменателя на GCF. В този раздел са включени номера до 25.

Улеснете по-доброто разбиране на GCF, като прегледате уменията си с този пакет от работни листове, които могат да се отпечатват и съдържат числа до 99. Практикувайте намирането на GCF и опростяването на фракцията с помощта на GCF.

В този набор от работни листове за pdf за 7-ми и 8-ми клас определете GCF за набора от три числа. Приложете метода за главно разлагане на факторизация, за да изброите често срещаните фактори. Умножете общите фактори, за да получите GCF на трите числа.

Време е да се запознаете с GCF на три числа, като изработите упражненията в тези pdfs, обхващащи числа до 99. Разработете GCF, като намерите произведението на основните фактори, общи за всичките три числа.

Получете задълбочени познания за намиране на най-големия общ фактор на полиноми с тези работни листове за гимназия, налични в лесни и умерени нива, намерете GCF на два или три монома, GCF на полиноми, намерете GCF, използвайки метода на разделяне и други!


Съдържание

Определение Редактиране

The най-големият общ делител (GCD) на две ненулеви цели числа a и b е най-голямото положително цяло число d такова, че d е делител както на a, така и на b, т.е. има цели числа e и f такива, че а = де и б = df , а d е най-голямото такова цяло число. GCD на a и b обикновено се означава gcd (а, б) . [9]

Тази дефиниция се прилага и когато едно от a и b е нула. В този случай GCD е абсолютната стойност на ненулевото цяло число: gcd (а, 0) = gcd (0, а) = | а | . Този случай е важен като крайна стъпка на евклидовия алгоритъм.

Горната дефиниция не може да се използва за дефиниране на gcd (0, 0), тъй като 0 × н = 0 и по този начин нулата няма най-голям делител. Нулата обаче е нейният най-голям делител, ако най велик се разбира в контекста на връзката на делимост, така че gcd (0, 0) обикновено се определя като 0. Това запазва обичайните идентичности за GCD, и по-специално идентичността на Bézout, а именно, че gcd (а, б) генерира същия идеал като <а, б>. [10] [11] [12] Тази конвенция се следва от много системи за компютърна алгебра. [13] Независимо от това, някои автори оставят gcd (0, 0) недефиниран. [14]

GCD на a и b е най-големият им положителен общ делител в връзката на предразпределението на делимостта. Това означава, че общите делители на a и b са точно делителите на техния GCD. Това обикновено се доказва чрез използване на левмата на Евклид, основната теорема за аритметиката или евклидовия алгоритъм. Това е значението на „най-голямото“, което се използва за обобщаване на концепцията за GCD.

Пример за редактиране

Числото 54 може да се изрази като произведение на две цели числа по няколко различни начина:

54 × 1 = 27 × 2 = 18 × 3 = 9 × 6.

От тях най-големият е 6, така че е най-големият общ делител:

Изчисляването на всички делители на двете числа по този начин обикновено не е ефективно, особено за големи числа, които имат много делители. Много по-ефективни методи са описани в § Изчисляване.

Съвместни номера Редактиране

Две числа се наричат ​​относително прости или съвместни, ако най-големият им общ делител е равен на 1. [15] Например 9 и 28 са относително прости.

Геометричен изглед Редактиране

Например, правоъгълна площ 24 на 60 може да бъде разделена на мрежа от: квадрати 1 на 1, квадрати 2 на 2, квадрати 3 на 3, квадрати 4 на 4, 6 на -6 квадрата или 12 на 12 квадрата. Следователно 12 е най-големият общ делител на 24 и 60. По този начин правоъгълна площ 24 на 60 може да бъде разделена на мрежа от квадратчета 12 на 12, с два квадрата по един ръб (24/12 = 2) и пет квадрата по другия (60/12 = 5).

Намаляване на фракциите Редактиране

Най-големият общ делител е полезен за намаляване на фракциите до най-ниските членове. [16] Например gcd (42, 56) = 14, следователно,

Най-малко често срещано редактиране

Най-големият общ делител може да се използва за намиране на най-малкото общо кратно на две числа, когато е известен най-големият общ делител, като се използва релацията, [1]

Използване на основни факторизации Редактиране

Най-големите общи делители могат да бъдат изчислени чрез определяне на простите факторизации на двете числа и сравняване на факторите. Например, за да изчислим gcd (48, 180), намираме основните факторизации 48 = 2 4 · 3 1 и 180 = 2 2 · 3 2 · 5 1, след което GCD е 2 min (4,2) · 3 min ( 1,2) · 5 мин (0,1) = 2 2 · 3 1 · 5 0 = 12, както е показано на диаграмата на Вен. Тогава съответният LCM е 2 max (4,2) · 3 max (1,2) · 5 max (0,1) = 2 4 · 3 2 · 5 1 = 720.

На практика този метод е изпълним само за малки числа, тъй като изчисляването на прости факторизации отнема твърде много време.

Алгоритъм на Евклид Редактиране

Методът, въведен от Евклид за изчисляване на най-често срещаните делители, се основава на факта, че при две положителни цели числа a и b такива, че а & gt б , общите делители на a и b са същите като общите делители на аб и б.

И така, методът на Евклид за изчисляване на най-големия общ делител на две положителни числа се състои в замяна на по-голямото число с разликата в числата и повтарянето му, докато двете числа са равни: това е най-големият им общ делител.

Например, за да се изчисли gcd (48,18), се процедира по следния начин:

Този метод може да бъде много бавен, ако едното число е много по-голямо от другото. Така че вариантът, който следва, обикновено е предпочитан.

Евклидов алгоритъм Редактиране

По-ефективен метод е Евклидов алгоритъм, вариант, при който разликата на двете числа a и b се заменя с остатък на евклидовата дивизия (наричана още деление с остатък) на a от b.

Означавайки този остатък като а мод б , алгоритъмът замества (а, б) от (б, а мод б), докато двойката е (д, 0), където d е най-големият общ делител.

Например, за да се изчисли gcd (48,18), изчислението е както следва:

Това отново дава gcd (48, 18) = 6.

Алгоритъм на GCD на Лемер Редактиране

Алгоритъмът на Лемер се основава на наблюдението, че първоначалните коефициенти, произведени от алгоритъма на Евклид, могат да бъдат определени въз основа само на първите няколко цифри, което е полезно за числа, които са по-големи от компютърна дума. По същество човек извлича начални цифри, обикновено образуващи една или две компютърни думи, и изпълнява алгоритмите на Евклид върху тези по-малки числа, стига да е гарантирано, че коефициентите са еднакви с тези, които биха били получени с оригиналните числа. Тези коефициенти се събират в малка матрица за преобразуване 2 на 2 (това е матрица от цели думи с една дума), за да се използват всички наведнъж за намаляване на първоначалните числа [ необходимо е разяснение ]. Този процес се повтаря, докато числата не са достатъчно малки, за да бъде двоичният алгоритъм (виж по-долу) по-ефективен.

Този алгоритъм подобрява скоростта, тъй като намалява броя на операциите при много големи числа и може да използва хардуерна аритметика за повечето операции. Всъщност повечето от коефициентите са много малки, така че справедлив брой стъпки от евклидовия алгоритъм могат да бъдат събрани в матрица 2 по 2 от цели думи с една дума. Когато алгоритъмът на Lehmer срещне твърде голям коефициент, той трябва да се върне към една итерация на евклидов алгоритъм, с евклидово деление на големи числа.

Двоичен GCD алгоритъм Редактиране

Двоичният GCD алгоритъм използва само изваждане и деление на 2. Методът е както следва: Нека а и б да са двете неотрицателни цели числа. Оставете цялото число д be 0. Има пет възможности:

Като gcd (а, а) = а, желаният GCD е а × 2 д (като а и б се променят в останалите случаи и д записва колко пъти това а и б са разделени на 2 в следващата стъпка, GCD на първоначалната двойка е продукт на а и 2 д ).

Тогава 2 е общ делител. Разделете и двете а и б с 2, увеличение д с 1, за да запишете колко пъти 2 е общ делител и продължете.

Тогава 2 не е общ делител. Разделям а с 2 и продължете.

Тогава 2 не е общ делител. Разделям б с 2 и продължете.

Като gcd (а,б) = gcd (б,а), ако а & lt б след това обмен а и б. Броя ° С = аб е положителен и по-малък от а. Всяко число, което се дели а и б също трябва да разделя ° С така че всеки общ делител на а и б също е общ делител на б и ° С. По същия начин, а = б + ° С и всеки общ делител на б и ° С също е общ делител на а и б. Така че двете двойки (а, б) и (б, ° С) имат еднакви общи делители и по този начин gcd (а,б) = gcd (б,° С). Освен това, както а и б и двете са странни, ° С е равномерно, процесът може да продължи с двойката (а, б) заменени с по-малките числа (° С/2, б) без промяна на GCD.

Всяка от горните стъпки намалява поне една от а и б като същевременно ги оставя неотрицателни и така може да се повтори само ограничен брой пъти. Така в крайна сметка процесът води до а = б, случаят на спиране. Тогава GCD е а × 2 д .

Пример: (а, б, д) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) по този начин оригиналният GCD е продуктът 6 от 2 д = 2 1 и а= б= 3.

Двоичният GCD алгоритъм е особено лесен за изпълнение на двоични компютри. Неговата изчислителна сложност е

Сложността на изчисленията обикновено се дава по отношение на дължината n на входа. Тук тази дължина е n = log ⁡ a + log ⁡ b, < displaystyle n = log a + log b,> и по този начин сложността е

Други методи Редактиране

Ако а и б и двете са ненулеви, най-големият общ делител на а и б може да се изчисли, като се използва най-малкото общо кратно (LCM) на а и б:

но по-често LCM се изчислява от GCD.

което обобщава на а и б рационални числа или съизмерими реални числа.

Кийт Славин показа това странно а ≥ 1:

което е функция, която може да бъде оценена за сложна б. [18] Волфганг Шрам показа това

е цяла функция в променливата б за всички положителни цели числа а където ° Сд(к) е сумата на Рамануджан. [19]

Сложност Редактиране

Сложността на изчисленията на изчисленията на най-често срещаните делители е широко проучена. [20] Ако някой използва евклидовия алгоритъм и елементарните алгоритми за умножение и деление, изчисляването на най-големия общ делител на две цели числа от най-много n бита е O (n 2). < displaystyle O (n ^ <2>).> Това означава, че изчисляването на най-големия общ делител има до постоянен коефициент същата сложност като умножението.

Ако обаче се използва алгоритъм за бързо умножение, човек може да модифицира евклидовия алгоритъм за подобряване на сложността, но изчисляването на най-големия общ делител става по-бавно от умножението. По-точно, ако умножението на две цели числа от n бита отнема време от T(н), тогава най-бързият известен алгоритъм за най-големия общ делител има сложност O (T (n) log ⁡ n). < displaystyle O left (T (n) log n right).> Това означава, че най-бързият известен алгоритъм има сложност на O (n (log ⁡ n) 2). < displaystyle O ляво (n , ( log n) ^ <2> дясно).>

Предишните сложности са валидни за обичайните модели на изчисления, по-специално многолентови машини на Тюринг и машини с произволен достъп.

По този начин изчисляването на най-големите общи делители принадлежи към класа на проблемите, разрешими в квазилинейно време. A fortiori, съответната задача за решение принадлежи към клас P на задачи, разрешими в полиномиално време. Не е известно, че проблемът с GCD е в NC, така че не е известен начин за ефективното му паралелизиране, нито е известно, че е P-пълен, което би означавало, че е малко вероятно да бъде възможно ефективно паралелизиране на GCD изчислението. Shallcross и сътр. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables if either problem is in NC or is P-complete, the other is as well. [21] Since NC contains NL, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.

Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in О(н/log н) time with н 1+ε processors. [22] Randomized algorithms can solve the problem in О((log н) 2 ) time on exp ⁡ ( O ( n log ⁡ n ) ) > ight) ight)> processors [ необходимо е разяснение ] (this is superpolynomial). [23]

  • Every common divisor of а и б is a divisor of gcd(а, б) .
  • gcd(а, б) , where а и б are not both zero, may be defined alternatively and equivalently as the smallest positive integer д which can be written in the form д = астр + бq , където стр и q са цели числа. This expression is called Bézout's identity. Числа стр и q like this can be computed with the extended Euclidean algorithm.
  • gcd(а, 0) = | а | , за а ≠ 0 , since any number is a divisor of 0, and the greatest divisor of а is | а |. [3][6] This is usually used as the base case in the Euclidean algorithm.
  • Ако а divides the product б° С, and gcd(а, б) = д , тогава а/д divides ° С.
  • Ако м is a non-negative integer, then gcd(ма, мб) = м⋅gcd(а, б) .
  • Ако м is any integer, then gcd(а + мб, б) = gcd(а, б) .
  • Ако м is a positive common divisor of а и б, then gcd(а/м, б/м) = gcd(а, б)/м .
  • The GCD is a multiplicative function in the following sense: if а1 и а2 are relatively prime, then gcd(а1а2, б) = gcd(а1, б)⋅gcd(а2, б). In particular, recalling that GCD is a positive integer valued function we obtain that gcd(а, б° С) = 1 if and only if gcd(а, б) = 1 and gcd(а, ° С) = 1 .
  • The GCD is a commutative function: gcd(а, б) = gcd(б, а) .
  • The GCD is an associative function: gcd(а, gcd(б, ° С)) = gcd(gcd(а, б), ° С). Thus gcd(а, б, ° С, . ) can be used to denote the GCD of multiple arguments.
  • gcd(а, б) is closely related to the least common multiple lcm(а, б) : we have gcd(а, б)⋅lcm(а, б) = | аб | .
  • The following versions of distributivity hold true: gcd(а, lcm(б, ° С)) = lcm(gcd(а, б), gcd(а, ° С)) lcm(а, gcd(б, ° С)) = gcd(lcm(а, б), lcm(а, ° С)) .
  • If we have the unique prime factorizations of а = стр1д1стр2д2 ⋅⋅⋅ стрмдм и б = стр1е1стр2е2 ⋅⋅⋅ стрмем където дi ≥ 0 и еi ≥ 0 , then the GCD of а и б is gcd(а,б) = стр1 min(д1,е1) стр2 min(д2,е2) ⋅⋅⋅ стрм min(дм,ем) .
  • It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a completedistributive lattice with GCD as meet and LCM as join operation. [24] This extension of the definition is also compatible with the generalization for commutative rings given below.
  • In a Cartesian coordinate system, gcd(а, б) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (а, б) .
  • For non-negative integers а и б, където а и б are not both zero, provable by considering the Euclidean algorithm in base н: [25] gcd(на − 1, нб − 1) = н gcd(а,б) − 1 .
  • An identity involving Euler's totient function: gcd ( a , b ) = ∑ k | a and k | b φ ( k ) . >k|b>varphi (k).>

In 1972, James E. Nymann showed that к integers, chosen independently and uniformly from <1, . н>, are coprime with probability 1/ζ(к) as н goes to infinity, where ζ refers to the Riemann zeta function. [26] (See coprime for a derivation.) This result was extended in 1987 to show that the probability that к random integers have greatest common divisor д е д −k /ζ(к). [27]

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when к = 2. In this case the probability that the GCD equals д е д −2 /ζ(2), and since ζ(2) = π 2 /6 we have

This last summation is the harmonic series, which diverges. However, when к ≥ 3, the expected value is well-defined, and by the above argument, it is

За к = 3, this is approximately equal to 1.3684. За к = 4, it is approximately 1.1106.

The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.

If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that д·х = а и д·у = б). If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and б.

With this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two GCD's of a and b must be associate elements, since by definition either one must divide the other indeed if a GCD exists, any one of its associates is a GCD as well. Existence of a GCD is not assured in arbitrary integral domains. However, if R is a unique factorization domain, then any two elements have a GCD, and more generally this is true in GCD domains. If R is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when R = F[х] where F is a field, or when R is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.

The following is an example of an integral domain with two elements that do not have a GCD:

The elements 2 and 1 + √ −3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √ −3 , but they are not associated, so there is no greatest common divisor of a and б.

Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal generated by a and b , and is denoted simply (а, б). In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element д then this d is a greatest common divisor of a and б. But the ideal (а, б) can be useful even when there is no greatest common divisor of a and б. (Indeed, Ernst Kummer used this ideal as a replacement for a GCD in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d , whence the ring-theoretic term.)


Гледай видеото: Riyaziyyat 6 ci sinif sehife 16. En Kicik Ortaq Bolunen. EKOB. Rasim Aliyev (Декември 2021).