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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть ,

.

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

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

1) .

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

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