Теорема о делении на данное число делимого, делителя и остатка

1. Если при делении с остатком делимое и делитель делятся на какое-нибудь число, то и остаток делится на это же число.

2. Если остаток при делении и делитель делятся на какое-нибудь число, то и делимое делится на то же число. Наибольший общий делитель нескольких чисел

Общим делителем данных чисел называется число, на которое делятся все данные числа.

Наибольшим общим делителем данных чисел называется наибольший из их общих делителей.

Наибольший общий делитель (N) чисел a, b, …, e обозначается символом

(a; b; …; e) = N.

Для сокращения вместо выражения "наибольший общий делитель" часто пишут только начальные буквы этих слов НОД.

Пример: НОД (35; 25) = 5.

Взаимно простые числа

Взаимно простыми числами называются те числа, наибольший общий делитель которых есть единица.

Если НОД (a; b; c; …) = 1, то числа a, b, c, … - взаимно простые.

Если каждое из чисел a, b, c, … оказывается взаимно простым с каждым другим из них, то числа a, b, c, … называются попарно простыми. Очевидно, что в случае двух чисел понятия "взаимно простые" и "попарно простые" совпадают.

Пример 1. Числа 29, 53, 100, 104 - взаимно простые, так как, кроме 1, они не имеют никакого общего делителя НОД (29; 53; 100; 104) = 1.

Пример 2. Числа 24, 17, 11 не только взаимно простые, но и попарно простые; действительно, НОД (24; 17) = НОД (24; 11) = НОД (17; 11) = 1.

Теоремы, на которых основано нахождение наибольшего общего делителя

1. Случай, когда два числа делятся одно на другое

Теорема. Если одно из двух данных чисел делится на другое, то меньшее из них есть их наибольший общий делитель.

2. Случай, когда два числа не делятся одно на другое

Теорема. Если большее из двух данных чисел не делится на меньшее, то их наибольшим общим делителем будет наибольший общий делитель меньшего числа и остатка от деления большего числа на меньшее.

Даны числа: 8084 и 1504;

Если оба слагаемых делятся на 188, тол и сумма 8084 делится на это же число. И это число есть наибольший общий делитель чисел 8084 и 1504. Если бы эти числа имели общий делитель больший 188, то он был бы делителем и 564, а для 564 и 1504 делитель 188 является наибольшим: 8084 : 188 = 43; 1504 : 188 = 8.

Алгоритм Евклида

Под алгоритмом будем понимать последовательность правил, строго следуя которым можно решить ту или иную задачу.

Задача будет считаться решенной, если для ее решения установлен определенный алгоритм.

Алгоритм Евклида служит для отыскания наибольшего общего делителя двух чисел способом последовательного деления.

Пусть a и b - натуральные числа, причем a > b и a не делится на b.

Допустим, что:

1) ,

2) ,

3) ,

4) ,

…………………………………………………………………….

n) ,

n + 1) .

Ряд равенств:

, , , , …, , , выражающих зависимость между делимым, делителем, частным и остатком при последовательном делении большего числа на меньшее, меньшего на первый остаток, первого остатка на второй остаток и т. д., известен под названием алгоритма Евклида.

Рассматриваемый ряд равенств конечен. В самом деле, по смыслу деления ряд остатков (следовательно, и ряд делителей) есть ряд убывающих целых чисел, который обязательно должен закончиться некоторым остатком , вследствие того, что число возможных остатков конечно, так как оно не может быть больше числа b. Итак, каковы бы ни были числа a и b, в результате последовательного деления большего числа на меньшее, меньшего на первый остаток, первого остатка на второй остаток и т. д., мы обязательно получим некоторый остаток , на который предыдущий остаток разделится без остатка, и, следовательно, число будет последним, не равным нулю остатком, а значит, т последним делителем. Таким образом, возможность дальнейшего деления отпадает.

Пример. Найти НОД чисел 852 и 192.

Решение

1. Делим большее число на меньшее:

2. Делим делитель 192 на остаток 84:

3. Новый делитель делим на полученный остаток:

4. Снова делитель делим на остаток:

В остатке получился нуль, значит процесс деления следует прекратить. Последний делитель (12) и будет наибольшим общим делителем чисел 852 и 192.

Ответ: НОД (852, 192) = 12

Правило для нахождения НОД двух чисел способом последовательного деления.

Теорема. Чтобы найти НОД двух чисел способом последовательного деления, надо большее из данных чисел разделить на меньшее, затем, меньшее - на первый остаток, первый остаток - на второй, второй - на третий и т. д. до тех пор, пока не получится в остатке 0. Тогда последний делитель (иначе, последний не равный нулю остаток) будет наибольшим общим делителем данных чисел.

Евклид применял свой алгоритм не только в арифметике, но и в геометрии для отыскания общей меры двух отрезков путем последовательного наложения.