Чтобы научиться находить наибольший общий делитель двух или нескольких чисел, необходимо разобраться с тем, что представляют из себя натуральные, простые и сложные числа.
Натуральным называется любое число, которое используется при подсчете целых предметов.
Если натуральное число можно разделить только на само себя и единицу, то его называют простым.
Все натуральные числа можно разделить на себя и единицу, однако единственным четным простым числом является 2, все остальные можно поделить на двойку. Поэтому простыми могут быть только нечетные числа.
Простых чисел достаточно много, полного списка их не существует. Для нахождения НОД удобно использовать специальные таблицы с такими числами.
Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.
Таким образом, делитель любого А - это число, на которое оно может быть разделено без остатка. Если у числа имеется более двух натуральных делителей, его называют составным.
У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.
Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел - 15.
Таким образом, общим делителем чисел А и Б называется такое число, на которое можно поделить их нацело. Наибольшим можно считать максимальное общее число, на которое можно их разделить.
Для решения задач используется такая сокращенная надпись:
НОД (А; Б).
Например, НОД (15; 30) = 30.
Чтобы записать все делители натурального числа, применяется запись:
Д (15) = {1, 3, 5, 15}
НОД (9; 15) = 1
В данном примере у натуральных чисел имеется только один общий делитель. Их называют взаимно простыми, соответственно единица и является их наибольшим общим делителем.
Как найти наибольший общий делитель чисел
Чтобы найти НОД нескольких чисел, нужно:
Найти все делители каждого натурального числа по отдельности, то есть разложить их на множители (простые числа);
Выделить все одинаковые множители у данных чисел;
Перемножить их между собой.
Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:
Чтобы не путаться при , удобно записывать множители при помощи вертикальных столбиков. В левой части от черты нужно разместить делимое, а в правой - делитель. Под делимым следует указать получившееся частное.
Так, в правом столбце окажутся все нужные для решения множители.
Одинаковые делители (найденные множители) можно для удобства подчеркнуть. Их следует переписать и перемножить и записать наибольший общий делитель.
НОД (30; 56) = 2 * 5 = 10
Вот так просто на самом деле найти наибольший общий делитель чисел. Если немного потренироваться, делать это можно будет практически на автомате.
Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.
Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение , используемое в математике.
Общие понятия и определения
Необходимо знать:
- Если некое число можно использовать для подсчёта различных предметов, например, девять столбов, шестнадцать домов, то оно является натуральным. Самым маленьким из них будет единица.
- Когда натуральное число делится на другое натуральное число, то говорят, что меньшее число - это делитель большего.
- Если два и более различных числа делятся на некое число без остатка, то говорят, что последнее будет их общим делителем (ОД).
- Самый большой из ОД именуется наибольшим общим делителем (НОД).
- В таком случае, когда у числа есть только два натуральных делителя (оно само и единичка), оно называется простым. Самое маленькое среди них - двойка, к тому же она и единственное чётное в их ряду.
- В случае если у двух чисел максимальным общим делителем является единица, то они будут взаимно простыми.
- Число, у которого больше чем два делителя, именуется составным.
- Процесс когда находятся все простые множители, которые при умножении между собой дадут в произведении начальное значение в математике называют разложением на простые множители. Причём одинаковые множители в разложении могут встречаться неоднократно.
В математике приняты следующие записи:
- Делители Д (45) = (1;3;5;9;45).
- ОД (8;18) = (1;2).
- НОД (8;18) = 2.
Различные способы найти НОД
Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.
Например, НОД (15;45) = 15, НОД (48;24) = 24.
Но такие случаи в математике являются весьма редкими, поэтому для того, чтобы находить НОД используются более сложные приёмы, хотя проверять этот вариант перед началом работы все же весьма рекомендуется.
Способ разложения на простые сомножители
Если необходимо найти НОД двух или более различных чисел , достаточно разложить каждое из них на простые сомножители, а затем произвести процесс умножения тех из них, которые имеются в каждом из чисел.
Пример 1
Рассмотрим, как находить НОД 36 и 90:
- 36 = 1*2*2*3*3;
- 90 = 1*2*3*3*5;
НОД (36;90) = 1*2*3*3 = 18.
Теперь посмотрим как находить то же самое в случае трёх чисел , возьмём для примера 54; 162; 42.
Как разложить 36 мы уже знаем, разберёмся с остальными:
- 162 = 1*2*3*3*3*3;
- 42 = 1*2*3*7;
Таким образом, НОД (36;162;42) = 1*2*3 = 6.
Следует заметить, что единицу в разложении писать совершенно необязательно.
Рассмотрим способ, как просто раскладывать на простые множители , для этого слева запишем необходимую нам цифру, а справа станем писать простые делители.
Разделять колонки можно, как знаком деления, так и простой вертикальной чертой.
- 36 / 2 продолжим наш процесс деления;
- 18 / 2 далее;
- 9 / 3 и ещё раз;
- 3 / 3 сейчас совсем элементарно;
- 1 - результат готов.
Искомое 36 = 2*2*3*3.
Евклидов способ
Этот вариант известен человечеству ещё со времён древнегреческой цивилизации, он во многом проще, и приписывается великому математику Евклиду, хотя весьма похожие алгоритмы применялись и ранее. Этот способ заключается в использовании следующего алгоритма , мы делим большее число с остатком на меньшее. Затем наш делитель делим на остаток и продолжаем так действовать по кругу пока не произойдёт деление нацело. Последнее значение и окажется искомым наибольшим общим делителем.
Приведём пример использования данного алгоритма :
попробуем выяснить какой НОД у 816 и 252:
- 816 / 252 = 3 и остаток 60. Сейчас 252 разделим на 60;
- 252 / 60 = 4 в остатке на этот раз окажется 12. Продолжим наш круговой процесс, разделим шестьдесят на двенадцать;
- 60 / 12 = 5. Поскольку на сей раз никакого остатка мы не получили, то у нас готов результат, двенадцать будет искомым для нас значением.
Итак, по завершении нашего процесса мы получили НОД (816;252) = 12.
Действия при необходимости определения НОД если задано более двух значений
Мы уже разобрались, что делать в случае, когда имеется два различных числа, теперь научимся действовать, если их имеется 3 и более .
При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.
Заключение
Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.
Хотя оба способа и являются вполне приемлемыми, в общеобразовательной школе гораздо чаще применяется первый способ . Это связано с тем, что разложение на простые множители понадобится при изучении следующей учебной темы - определение наибольшего общего кратного (НОК). Но все же стоит ещё раз заметить - применение алгоритма Евклида ни в коей мере не может считаться ошибочным.
Видео
С помощью видео вы сможете узнать, как найти наибольший общий делитель.
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Алгоритм нахождения НОД делением
- Большее число делим на меньшее.
- Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
- Если есть остаток, то большее число заменяем на остаток от деления.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6
a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)
В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.
Алгоритм нахождения НОД вычитанием
- Из большего числа вычитаем меньшее.
- Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
- Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6
a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)
Найдем наибольший общий делитель НОД (36 ; 24)
Этапы решения
Способ №1
36
- составное число
24
- составное число
Разложим число 36
36:
2
= 18
18:
2
= 9
- делится на простое число 2
9:
3
=
3
- делится на простое число 3.
Разложим число 24 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
24:
2
= 12
- делится на простое число 2
12:
2
= 6
- делится на простое число 2
6:
2
=
3
Завершаем деление, так как 3 простое число
2) Выделим синим цветом и выпишем общие множители
36
=
2
⋅
2
⋅
3
⋅
3
24
=
2
⋅
2
⋅
2
⋅
3
Общие множители (36 ; 24) : 2, 2, 3
3) Теперь, чтобы найти НОД нужно перемножить общие множители
Ответ: НОД (36 ; 24) = 2 ∙ 2 ∙ 3 = 12
Способ №2
1) Найдем все возможные делители чисел (36 ; 24). Для этого поочередно разделим число 36 на делители от 1 до 36, число 24 на делители от 1 до 24. Если число делится без остатка, то делитель запишем в список делителей.
Для числа
36
36:
1
= 36;
36:
2
= 18;
36:
3
= 12;
36:
4
= 9;
36:
6
= 6;
36:
9
= 4;
36:
12
= 3;
36:
18
= 2;
36:
36
= 1;
Для числа
24
выпишем все случаи, когда оно делится без остатка:
24:
1
= 24;
24:
2
= 12;
24:
3
= 8;
24:
4
= 6;
24:
6
= 4;
24:
8
= 3;
24:
12
= 2;
24:
24
= 1;
2) Выпишем все общие делители чисел (36 ; 24) и выделим зеленым цветом самы большой, это и будет наибольший общий делитель НОД чисел (36 ; 24)
Общие делители чисел (36 ; 24): 1, 2, 3, 4, 6, 12
Ответ: НОД (36 ; 24) = 12
Найдем наименьшее общее кратное НОК (52 ; 49)
Этапы решения
Способ №1
1) Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением)
52
- составное число
49
- составное число
Разложим число 52 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
52:
2
= 26
- делится на простое число 2
26:
2
=
13
- делится на простое число 2.
Завершаем деление, так как 13 простое число
Разложим число 49 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
49:
7
=
7
- делится на простое число 7.
Завершаем деление, так как 7 простое число
2) Прежде всего запишем множители самого большого числа, а затем меньшего числа. Найдем недостающие множители, выделим синим цветом в разложении меньшего числа множители, которые не вошли в разложение большего числа.
52
= 2 ∙ 2 ∙ 13
49
=
7
∙
7
3) Теперь, чтобы найти НОК нужно перемножить множители большего числа с недостающими множителями, которые выделены синим цветом
НОК (52 ; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548
Способ №2
1) Найдем все возможные кратные чисел (52 ; 49). Для этого поочередно умножим число 52 на числа от 1 до 49, число 49 на числа от 1 до 52.
Выделим все кратные числа 52 зеленым цветом:
52 ∙ 1 =
52
;
52 ∙ 2 =
104
;
52 ∙ 3 =
156
;
52 ∙ 4 =
208
;
52 ∙ 5 =
260
;
52 ∙ 6 =
312
;
52 ∙ 7 =
364
;
52 ∙ 8 =
416
;
52 ∙ 9 =
468
;
52 ∙ 10 =
520
;
52 ∙ 11 =
572
;
52 ∙ 12 =
624
;
52 ∙ 13 =
676
;
52 ∙ 14 =
728
;
52 ∙ 15 =
780
;
52 ∙ 16 =
832
;
52 ∙ 17 =
884
;
52 ∙ 18 =
936
;
52 ∙ 19 =
988
;
52 ∙ 20 =
1040
;
52 ∙ 21 =
1092
;
52 ∙ 22 =
1144
;
52 ∙ 23 =
1196
;
52 ∙ 24 =
1248
;
52 ∙ 25 =
1300
;
52 ∙ 26 =
1352
;
52 ∙ 27 =
1404
;
52 ∙ 28 =
1456
;
52 ∙ 29 =
1508
;
52 ∙ 30 =
1560
;
52 ∙ 31 =
1612
;
52 ∙ 32 =
1664
;
52 ∙ 33 =
1716
;
52 ∙ 34 =
1768
;
52 ∙ 35 =
1820
;
52 ∙ 36 =
1872
;
52 ∙ 37 =
1924
;
52 ∙ 38 =
1976
;
52 ∙ 39 =
2028
;
52 ∙ 40 =
2080
;
52 ∙ 41 =
2132
;
52 ∙ 42 =
2184
;
52 ∙ 43 =
2236
;
52 ∙ 44 =
2288
;
52 ∙ 45 =
2340
;
52 ∙ 46 =
2392
;
52 ∙ 47 =
2444
;
52 ∙ 48 =
2496
;
52 ∙ 49 =
2548
;
Выделим все кратные числа 49 зеленым цветом:
49 ∙ 1 =
49
;
49 ∙ 2 =
98
;
49 ∙ 3 =
147
;
49 ∙ 4 =
196
;
49 ∙ 5 =
245
;
49 ∙ 6 =
294
;
49 ∙ 7 =
343
;
49 ∙ 8 =
392
;
49 ∙ 9 =
441
;
49 ∙ 10 =
490
;
49 ∙ 11 =
539
;
49 ∙ 12 =
588
;
49 ∙ 13 =
637
;
49 ∙ 14 =
686
;
49 ∙ 15 =
735
;
49 ∙ 16 =
784
;
49 ∙ 17 =
833
;
49 ∙ 18 =
882
;
49 ∙ 19 =
931
;
49 ∙ 20 =
980
;
49 ∙ 21 =
1029
;
49 ∙ 22 =
1078
;
49 ∙ 23 =
1127
;
49 ∙ 24 =
1176
;
49 ∙ 25 =
1225
;
49 ∙ 26 =
1274
;
49 ∙ 27 =
1323
;
49 ∙ 28 =
1372
;
49 ∙ 29 =
1421
;
49 ∙ 30 =
1470
;
49 ∙ 31 =
1519
;
49 ∙ 32 =
1568
;
49 ∙ 33 =
1617
;
49 ∙ 34 =
1666
;
49 ∙ 35 =
1715
;
49 ∙ 36 =
1764
;
49 ∙ 37 =
1813
;
49 ∙ 38 =
1862
;
49 ∙ 39 =
1911
;
49 ∙ 40 =
1960
;
49 ∙ 41 =
2009
;
49 ∙ 42 =
2058
;
49 ∙ 43 =
2107
;
49 ∙ 44 =
2156
;
49 ∙ 45 =
2205
;
49 ∙ 46 =
2254
;
49 ∙ 47 =
2303
;
49 ∙ 48 =
2352
;
49 ∙ 49 =
2401
;
49 ∙ 50 =
2450
;
49 ∙ 51 =
2499
;
49 ∙ 52 =
2548
;
2) Выпишем все общие кратные чисел (52 ; 49) и выделим зеленым цветом самое маленькое, это и будет наименьшим общим кратным чисел (52 ; 49).
Общие кратные чисел (52 ; 49): 2548
Ответ: НОК (52 ; 49) = 2548
Сейчас и в дальнейшем мы будем подразумевать, что хотя бы одно из данных чисел отлично от нуля. Если все данные числа равны нулю, то их общим делителем является любое целое число, а так как целых чисел бесконечно много, то мы не можем говорить о наибольшем из них. Следовательно, нельзя говорить о наибольшем общем делителе чисел, каждое из которых равно нулю.
Теперь мы можем дать определение наибольшего общего делителя двух чисел.
Определение.
Наибольший общий делитель двух целых чисел – это наибольшее целое число, делящее два данных целых числа.
Для краткой записи наибольшего общего делителя часто используют аббревиатуру НОД – Наибольший Общий Делитель. Также наибольший общий делитель двух чисел a и b часто обозначают как НОД(a, b) .
Приведем пример наибольшего общего делителя (НОД) двух целых чисел. Наибольший общий делитель чисел 6 и −15 равен 3 . Обоснуем это. Запишем все делители числа шесть: ±6 , ±3 , ±1 , а делителями числа −15 являются числа ±15 , ±5 , ±3 и ±1 . Теперь можно найти все общие делители чисел 6 и −15 , это числа −3 , −1 , 1 и 3 . Так как −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Определение наибольшего общего делителя трех и большего количества целых чисел аналогично определению НОД двух чисел.
Определение.
Наибольший общий делитель трех и большего количества целых чисел – это наибольшее целое число, делящее одновременно все данные числа.
Наибольший общий делитель n целых чисел a 1 , a 2 , …, a n мы будем обозначать как НОД(a 1 , a 2 , …, a n) . Если найдено значение b наибольшего общего делителя этих чисел, то можно записать НОД(a 1 , a 2 , …, a n)=b .
В качестве примера приведем НОД четырех целых чисел −8 , 52 , 16 и −12 , он равен 4 , то есть, НОД(−8, 52, 16, −12)=4 . Это можно проверить, записав все делители данных чисел, выбрав из них общие и определив наибольший общий делитель.
Отметим, что наибольший общий делитель целых чисел может быть равен одному из этих чисел. Это утверждение справедливо в том случае, если все данные числа делятся на одно из них (доказательство приведено в следующем пункте этой статьи). Например, НОД(15, 60, −45)=15 . Это действительно так, так как 15 делит и число 15 , и число 60 , и число −45 , и не существует общего делителя чисел 15 , 60 и −45 , который превосходит 15 .
Особый интерес представляют так называемые взаимно простые числа , - такие целые числа, наибольший общий делитель которых равен единице.
Свойства наибольшего общего делителя, алгоритм Евклида
Наибольший общий делитель обладает рядом характерных результатов, иными словами, рядом свойств. Сейчас мы перечислим основные свойства наибольшего общего делителя (НОД) , формулировать их мы будем в виде теорем и сразу приводить доказательства.
Все свойства наибольшего общего делителя мы будем формулировать для положительных целых чисел, при этом будем рассматривать лишь положительные делители этих чисел.
Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a , то есть, НОД(a, b)=НОД(a, b) .
Это свойство НОД напрямую следует из определения наибольшего общего делителя.
Если a делится на b , то множество общих делителей чисел a и b совпадает со множеством делителей числа b , в частности, НОД(a, b)=b .
Доказательство.
Любой общий делитель чисел a и b является делителем каждого из этих чисел, в том числе и числа b . С другой стороны, так как a кратно b , то любой делитель числа b является делителем и числа a в силу того, что делимость обладает свойством транзитивности, следовательно, любой делитель числа b является общим делителем чисел a и b . Этим доказано, что если a делится на b , то совокупность делителей чисел a и b совпадает с совокупностью делителей одного числа b . А так как наибольшим делителем числа b является само число b , то наибольший общий делитель чисел a и b также равен b , то есть, НОД(a, b)=b .
В частности, если числа a и b равны, то НОД(a, b)=НОД(a, a)=НОД(b, b)=a=b . К примеру, НОД(132, 132)=132 .
Доказанное свойство наибольшего делителя позволяет нам находить НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число. Например, НОД(8, 24)=8 , так как 24 кратно восьми.
Если a=b·q+c , где a , b , c и q – целые числа, то множество общих делителей чисел a и b совпадает со множеством общих делителей чисел b и c , в частности, НОД(a, b)=НОД(b, c) .
Обоснуем это свойство НОД.
Так как имеет место равенство a=b·q+c , то всякий общий делитель чисел a и b делит также и c (это следует из свойств делимости). По этой же причине, всякий общий делитель чисел b и c делит a . Поэтому совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и c . В частности, должны совпадать и наибольшие из этих общих делителей, то есть, должно быть справедливо следующее равенство НОД(a, b)=НОД(b, c) .
Сейчас мы сформулируем и докажем теорему, которая представляет собой алгоритм Евклида . Алгоритм Евклида позволяет находить НОД двух чисел (смотрите нахождение НОД по алгоритму Евклида). Более того алгоритм Евклида позволит нам доказать приведенные ниже свойства наибольшего общего делителя.
Прежде чем дать формулировку теоремы, рекомендуем освежить в памяти теорему из раздела теории , которая утверждает, что делимое a может быть представлено в виде b·q+r , где b – делитель, q – некоторое целое число, называемое неполным частным, а r – целое число, удовлетворяющее условию , называемое остатком.
Итак, пусть для двух ненулевых целых положительных чисел a
и b
справедлив ряд равенств
заканчивающийся, когда r k+1 =0
(что неизбежно, так как b>r 1 >r 2 >r 3 , …
- ряд убывающих целых чисел, и этот ряд не может содержать более чем конечное число положительных чисел), тогда r k
– это наибольший общий делитель чисел a
и b
, то есть, r k =НОД(a, b)
.
Доказательство.
Докажем сначала, что r k является общим делителем чисел a и b , после чего покажем, что r k не просто делитель, а наибольший общий делитель чисел a и b .
Будем двигаться по записанным равенствам снизу вверх. Из последнего равенства можно сказать, что r k−1 делится на r k . Учитывая этот факт, а также предыдущее свойство НОД, предпоследнее равенство r k−2 =r k−1 ·q k +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 является общим делителем чисел a и b .
Осталось доказать, что r k =НОД(a, b) . Для достаточно показать, что любой общий делитель чисел a и b (обозначим его r 0 ) делит r k .
Будем двигаться по исходным равенствам сверху вниз. В силу предыдущего свойства из первого равенства следует, что r 1 делится на r 0 . Тогда из второго равенства получаем, что r 2 делится на r 0 . И так далее. Из последнего равенства получаем, что r k делится на r 0 . Таким образом, r k =НОД(a, b) .
Из рассмотренного свойства наибольшего общего делителя следует, что множество общих делителей чисел a и b совпадает с множеством делителей наибольшего общего делителя этих чисел. Это следствие из алгоритма Евклида позволяет найти все общие делители двух чисел как делители НОД этих чисел.
Пусть a и b – целые числа, одновременно не равные нулю, тогда существуют такие целые числа u 0 и v 0 , то справедливо равенство НОД(a, b)=a·u 0 +b·v 0 . Последнее равенство представляет собой линейное представление наибольшего общего делителя чисел a и b , это равенство называют соотношением Безу, а числа u 0 и v 0 – коэффициентами Безу.
Доказательство.
По алгоритму Евклида мы можем записать следующие равенства
Из первого равенства имеем 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 , и так далее. Наконец, r k =s k ·a+t k ·b , где s k и t k - целые. Так как r k =НОД(a, b) , и, обозначив s k =u 0 и t k =v 0 , получим линейное представление НОД требуемого вида: НОД(a, b)=a·u 0 +b·v 0 .
Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b) .
Обоснование этого свойства наибольшего общего делителя таково. Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД(m·a, m·b)=m·r k , а r k – это НОД(a, b) . Следовательно, НОД(m·a, m·b)=m·НОД(a, b) .
На этом свойстве наибольшего общего делителя основан способ нахождения НОД с помощью разложения на простые множители .
Пусть p – любой общий делитель чисел a и b , тогда НОД(a:p, b:p)=НОД(a, b):p , в частности, если p=НОД(a, b) имеем НОД(a:НОД(a, b), b:НОД(a, b))=1 , то есть, числа a:НОД(a, b) и b:НОД(a, b) - взаимно простые.
Так как a=p·(a:p) и b=p·(b:p) , и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД(a, b)=НОД(p·(a:p), p·(b:p))= p·НОД(a:p, b:p) , откуда и следует доказываемое равенство.
Только что доказанное свойство наибольшего общего делителя лежит в основе .
Сейчас озвучим свойство НОД, которое сводит задачу нахождения наибольшего общего делителя трех и большего количества чисел к последовательному отысканию НОД двух чисел.
Наибольший общий делитель чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .
Доказательство базируется на следствии из алгоритма Евклида. Общие делители чисел a 1 и a 2 совпадают с делителями d 2 . Тогда общие делители чисел a 1 , a 2 и a 3 совпадают с общими делителями чисел d 2 и a 3 , следовательно, совпадают с делителями d 3 . Общие делители чисел a 1 , a 2 , a 3 и a 4 совпадают с общими делителями d 3 и a 4 , следовательно, совпадают с делителями d 4 . И так далее. Наконец, общие делители чисел a 1 , a 2 , …, a k совпадают с делителями d k . А так как наибольшим делителем числа d k является само число d k , то НОД(a 1 , a 2 , …, a k)=d k .
На этом закончим обзор основных свойств наибольшего общего делителя.
Список литературы.
- Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
- Виноградов И.М. Основы теории чисел.
- Михелович Ш.Х. Теория чисел.
- Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.