Учебные материалы по математике | Алгоритм евклида | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


3) делится на любой общий делитель чисел .

Обозначается НОД чисел так: .

Теорема 1. Если НОД целых чисел существует, то он определяется однозначно.

Доказательство: Пусть и .

Так как — общий делитель , а — их НОД, то .

Так как — общий делитель , а — их НОД, то .

А так как , , то из и . ▲.

Теорема 2. НОД целых чисел равен НОД их модулей, то есть .

Поэтому в дальнейшем можно рассматривать НОД натуральных чисел.

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

Опишем способ отыскания НОД двух натуральных чисел, который носит название «алгоритм Евклида».

Пусть . Делим на с остатком: , .

Если , то процесс закончен и .

Если , то делим на с остатком: , .

Если , то процесс закончен, если , делим на : , .

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

Пусть ,

.

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

Доказательство: Пусть — последний отличный от нуля остаток, тогда:

1) .

2) Покажем, что — общий делитель чисел . Для этого рассмотрим последовательно равенства алгоритма Евклида, начиная с последнего. Из этого равенства следует, что

, кроме того, . Тогда , то есть ; затем получим, что и т. д. И, наконец, из второго и первого равенств имеем, что и .

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод