История появления натуральных чисел и нуля. Теоретико-множественное определение натурального числа и нуля. Теоретико-множественное определение сложения и разности целых неотрицательных чисел. Свойства сложения

Нахождение НОД трех и большего количества чисел

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a₁, a₂, …, a_k равен числу d_k, которое находится при последовательном вычислении НОД(a₁, a₂)=d₂,НОД(d₂, a₃)=d₃, НОД(d₃, a₄)=d₄, …, НОД(d_k-1, a_k)=d_k.
Давайте разберемся, как выглядит процесс нахождения НОД нескольких чисел, рассмотрев решение примера.
Пример.
Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.
Решение.
В этом примере a₁=78, a₂=294, a₃=570, a₄=36.
Сначала по алгоритму Евклида определим наибольший общий делитель d₂двух первых чисел 78 и 294. При делении получаем равенства 294=78·3+60;78=60·1+18; 60=18·3+6 и 18=6·3. Таким образом, d₂=НОД(78, 294)=6.
Теперь вычислим d₃=НОД(d₂, a₃)=НОД(6, 570). Опять применим алгоритм Евклида: 570=6·95, следовательно, d₃=НОД(6, 570)=6.
Осталось вычислить d₄=НОД(d₃, a₄)=НОД(6, 36). Так как 36 делится на 6, тоd₄=НОД(6, 36)=6.
Таким образом, наибольший общий делитель четырех данных чисел равенd₄=6, то есть, НОД(78, 294, 570, 36)=6.
Ответ:
НОД(78, 294, 570, 36)=6.
Разложение чисел на простые множители также позволяет вычислять НОД трех и большего количества чисел. В этом случае наибольший общий делитель находится как произведение всех общих простых множителей данных чисел.
Пример.
Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.
Решение.
Разложим числа 78, 294, 570 и 36 на простые множители, получаем 78=2·3·13,294=2·3·7·7, 570=2·3·5·19, 36=2·2·3·3. Общими простыми множителями всех данных четырех чисел являются числа 2 и 3. Следовательно,НОД(78, 294, 570, 36)=2·3=6.
Ответ:
НОД(78, 294, 570, 36)=6.