Дана пара целых чисел (m,n). Считаем n остатком с номером 1. Первый шаг алгоритма Евклида – делим m на n с остатком, а далее делим остаток на вновь получившийся остаток, покуда этот вновь получившийся остаток не станет равным 0. Этот момент обязательно наступит, так как модули остатков строго убывают. Более точно: обозначим и образуем последовательность делений с остатком:
Для чего предназначен этот алгоритм? Например, для вычисления наибольшего общего делителя пары чисел m и n. Обозначим через НОД(m,n) – наибольшее натуральное число, делящее как m так и и n. Дополнительно, по определению полагаем НОД(0,0)=0.
Если то , т.е. согласно первой строке алгоритма. Но тогда d делит и и т.д. вплоть до . Эту цепочку импликаций можно обратить: если , то d делит , а затем делит и т.д. вплоть до n и m. Доказано, что
-- последний ненулевой остаток в алгоритме Евклида. Попробуем на практике, взяв m=900 и n=1155
Итог: НОД(900,1155)=15. Мы могли бы уменьшить числа, пользуясь правилом
Тогда НОД(900,1155)=5⋅ НОД(180,231)=15⋅ НОД(60,77). Но далее, применяя алгоритм Евклида, мы записали бы опять шесть строк и пришли к выводу, что НОД(60,77)=1. Числа m и n, наибольший общий делитель которых равен 1, называются взаимно простыми. Оказывается число d=НОД(m,n) можно записать в виде линейной комбинации своих аргументов:
Это важное соотношение позволяет доказать известное правило для простых чисел p:
из которого в свою очередь вытекает единственность разложения на простые множители. Однако, все по порядку: докажем сначала (2). Проходим еще раз по строкам алгоритма Евклида сверху в низ: -- выражается в виде линейной комбинации, тогда и
также выражается через m и n в виде линейной комбинации. Дойдя до последней строки, видим, что и выражается через m и n в виде линейной комбинации. Заметим, что если выполняется соотношение (2), то |d | заведомо есть НОД чисел m и n. Для чисел получаем:
Докажем теперь правило (3). Пусть , т.е. для некоторого k. Если , то все доказано. Иначе НОД(p, k)=1, ибо p простой элемент. Пользуясь (1), найдем элементы s,t такие, что 1=ps+at. Тогда
откуда .
Предположим теперь, что
-- два разложения в произведение простых элементов: простые и -- попарно различны. Доказательство ведем индукцией по числу . База индукции – случай s=t=1, очевиден. Так как делит произведение , то делит один из сомножителей . Но этот сомножитель также есть простой элемент и поэтому .
Сокращая левую и правую часть соотношения (4) на , получаем аналогичное равенство, но с меньшим числом сомножителей. Продолжая этот процесс, дойдем до равенства и, в частности, до равенства s=t. Этим и завершается доказательство основной теоремы арифметики.