Общее определение деления натуральных чисел

В множестве натуральных чисел делению без остатка и делению с остатком можно дать следующее определение:

Разделить число a на число b - значит найти такие два числа q (частное) и r (остаток), которые удовлетворяли бы соотношениям:

.

Из равенства следует, что

.

Так как r < b, то частное q показывает, какое наибольшее число раз делитель содержится в делимом. Если делитель b не равен нулю, то действие деление всегда возможно и всегда дает единственный результат.

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

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

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

Наибольший общий делитель нескольких чисел

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

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

Наибольший общий делитель (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.

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

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

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

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

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

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

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

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