Алгоритм Евклида для целых чисел

Свойства

Замечание: во всех формулах этого раздела предполагается, что — целые числа.

§ Любое целое число является делителем нуля, и частное равно нулю:

§ Любое целое число делится на единицу:

§ На ноль делится только ноль:

,

причём частное в этом случае не определено.

§ Единица делится только на единицу:

§ Для любого целого числа найдётся такое целое число для которого

§ Если и то Отсюда же следует, что если и то

§ Для того чтобы необходимо и достаточно, чтобы

§ Если то

§ Свойство делимости является отношением нестрогого порядка и, в частности, оно:

§ рефлексивно, т.е. любое целое число делится на себя же:

§ транзитивно, т.е. если и то

§ антисимметрично, т.е. если и то либо либо

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда НОД(a, b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

§ Пусть , тогда НОД (a, b) = НОД (b, r).

Дата добавления: 2015-04-24