Калькулятор алгоритма Евклида

a = q * b + r, поэтому НОД(a, b) = НОД(b, r); повторяйте, пока r = 0, — тогда ответом будет b

a = q * b + r

Один шаг алгоритма, записанный уравнением. a — большее из двух чисел на этом шаге, b — меньшее, q — сколько целых раз b укладывается в a, r — то, что осталось. Ровно так же выглядит и строка шагов на панели: 1 071 = 2 * 462 + 147 — это один шаг

a, b

Два сравниваемых числа. На каждом шаге они меняются ролями: b одного шага становится a следующего, а r — новым b. Из-за этой перестановки поля и названы первым и вторым числом, а не делимым и делителем: на первом шаге делимое — это 1 071, на втором — уже 462, и имя, верное для одного шага, ошибочно для остальных

q

Частное — сколько целых раз b укладывается в a. Оно всегда не меньше единицы, потому что пару перед началом цикла расставляют по убыванию; поэтому q = 0 здесь не встретится ни разу. Единственный шаг, где q ничем не примечательно, — последний: остаток равен нулю, и деление получается точным

r

Остаток, всегда меньше b и никогда не отрицательный. Условие остановки — r = 0, и оно печатается последним шагом, а не опускается: строка 147 = 7 * 21 + 0 и есть то сообщение, что поиск окончен и ответ 21

НОД(a, b)

Наибольший общий делитель: самое большое целое число, на которое делятся и a, и b без остатка. Ответ — это b последнего шага, взятое прямо из цикла, а не вычисленное заново. Для 1 071 и 462 это 21, поэтому 1 071 = 21 × 51 и 462 = 21 × 22, и никакое большее число на оба сразу не делится

610 = 1 * 377 + 233

Первый шаг худшего случая: соседние числа Фибоначчи. Каждое частное здесь равно единице, и числа почти не убывают — именно поэтому такая пара идёт тринадцать шагов. Теорема Ламе утверждает, что ни одна пара такого размера не может потребовать больше

Сокращение дроби — повседневный случай. Чтобы записать 462/1071 несократимо, нужен наибольший общий делитель этих двух чисел, и страница выдаёт его вместе с доказательством: 21 и три шага, которые к нему привели. Разделите верх и низ на 21 — получите 22/51, и напечатанные шаги позволяют проверить сокращение, а не поверить ему на слово. Та же нужда возникает всюду, где отношение надо упростить: передаточные числа, соотношения сторон экрана, масштаб чертежа и вообще любые две величины, которые хочется выразить пропорцией, а не парой чисел. Второе применение — в программировании и на занятиях, где этот алгоритм разбирают как первый по-настоящему интересный: он завершается, он быстрый, и его правильность видна из одного уравнения. Он же — стандартный способ посчитать обратный элемент по модулю (расширенная версия тащит через те же шаги два дополнительных числа), а это один из шагов при генерации ключей RSA. Третье применение — проверка перед разложением на множители: обнаружить, что 1 071 = 3 × 357, а 462 = 2 × 3 × 7 × 11, — это работа, а найти их общий делитель 21 — три деления, так что с этой страницы удобно начинать и заранее знать, будет ли сокращение лёгким. Когда нужен только ответ, а не процесс, страница «Калькулятор НОД» задаёт тот же вопрос в короткой форме и умеет больше двух чисел сразу; страница «Калькулятор НОК» берёт из общего делителя наименьшее общее кратное, потому что НОК = (a / НОД) × b; а что означает один остаток, когда числа могут быть отрицательными, разбирает страница «Калькулятор остатка» — здесь этого никогда не требуется.

1. Хрестоматийная пара: 1 071 и 462

   1. Сколько раз 462 укладывается в 1 071? Дважды: 2 × 462 = 924, и остаётся 1 071 − 924 = 147
   2. Теперь пара — 462 и 147: 147 укладывается в 462 трижды, 3 × 147 = 441, остаётся 21
   3. Теперь пара — 147 и 21: 21 укладывается в 147 ровно семь раз, остатка нет
   4. Остаток равен нулю, значит алгоритм останавливается, и ответ — 21

   Ввод по умолчанию и та самая пара, с которой этот алгоритм обычно и объясняют. По результату стоит сделать две проверки. Разделите оба числа на 21 — получите 51 и 22, у которых нет общих делителей; именно поэтому 21 наибольший делитель, а не просто один из общих. И обратите внимание, что разложения на множители здесь не было нигде: чтобы найти делители 1 071 перебором, пришлось бы дойти до 32, а алгоритм только делил число на то, что у него уже было на руках. Три шага, каждый дешевле предыдущего.

2. Одного шага достаточно: 12 и 60

   1. Расставьте пару по убыванию: 60 первым, 12 вторым
   2. 60 = 5 × 12 + 0, значит 12 делит 60 нацело
   3. Остаток нулевой сразу, поэтому алгоритм заканчивается после одного шага
   4. Ответ — 12, меньшее из двух чисел, потому что оно делит большее

   Самый короткий нетривиальный прогон: этот случай показывает, почему последний шаг печатается, а не пропускается. Строка 60 = 5 * 12 + 0 и есть весь ответ: она говорит, что остаток дошёл до нуля, а это единственный способ, которым алгоритм завершается. Уберите её — и шагов не останется вовсе, и читатель не сможет отличить ответ в один шаг от страницы, которая не считала. Когда одно число делит другое нацело, наибольший общий делитель — просто меньшее из них.

3. Взаимно простые числа: 9 и 20

   1. 20 = 2 × 9 + 2, поэтому пара становится 9 и 2
   2. 9 = 4 × 2 + 1, поэтому пара становится 2 и 1
   3. 2 = 2 × 1 + 0, и алгоритм останавливается
   4. Ответ — 1: значит, у 9 и 20 нет общих делителей, кроме единицы

   Наибольший общий делитель, равный единице, — полноценный ответ, а не неудача, и у него есть название: числа взаимно простые. Это же признак того, что дробь 9/20 уже несократима и упрощать в ней нечего. Заметьте, что шаги не свернулись: алгоритм прошёл до единицы за три шага, потому что ни одно из чисел не делило другое нацело. С ростом чисел взаимно простые пары — обычное дело: вероятность того, что два случайно взятых числа имеют общий делитель, падает быстро, и именно это делает метод пригодным для построения обратного элемента по модулю в криптографии.

Оба числа должны быть целыми и лежать в диапазоне от 1 до 1 000 000. Ноль отклоняется, а не трактуется как особый случай. Наибольший общий делитель a и 0 равен a, и это совершенно законный ответ, но показать его эта страница не может: первый же шаг выглядел бы как a = q * 0 + r, а такого q не существует. Вместо того чтобы печатать процесс с дырой, страница отказывается принимать ввод. По той же причине отклоняются отрицательные числа: напечатанные шаги предполагают, что оба числа не меньше единицы, а для отрицательного операнда понадобилось бы правило о том, что означают частное и остаток, которого эта страница нигде не формулирует. Потолок в 1 000 000 стоит не из-за алгоритма — он спокойно работал бы и с куда большими числами, — а ради того, чтобы каждое вычитание, умножение и остаток по дороге были точными в обычной арифметике двойной точности и чтобы напечатанные шаги не растянулись до нечитаемой длины. Два небольших числа всё равно могут дать много шагов: 610 и 377 идут тринадцать, — но на практике число шагов ограничено потолком, а в таблице ниже для этого есть отдельный столбец. Шаги печатаются уравнениями — a = q * b + r, соединёнными точками с запятой, — а не делением в столбик, так что привычной рамки с уголком здесь не будет. Вводить числа можно в любом порядке: страница сама расставляет их по убыванию, поэтому посмотреть, как выглядел бы шаг 3 = 0 * 5 + 3, на этой странице нельзя — такой шаг просто не возникает. Из того же правила следует ещё одно: первое и второе поле полностью взаимозаменяемы, и «делимое» с «делителем» на них не подписаны именно поэтому. Если ваши числа могут быть отрицательными или нужно точное соглашение о знаке остатка, это вопрос к странице «Калькулятор остатка».

Почему шаги заканчиваются строкой с нулевым остатком?

Потому что этот ноль — единственный выход из алгоритма. Цикл не считает заранее, сколько ему шагов: он делит, получает остаток и повторяет, пока остаток не станет нулём. Поэтому последняя строка печатается, а не пропускается — уберите её, и шаги просто оборвутся на ненулевом остатке, который читателю пришлось бы самому опознать как ответ. Строка 147 = 7 * 21 + 0 говорит прямо: поиск окончен, ответ 21.

Почему ответ равен второму числу, а не первому?

Потому что на последнем шаге роль делителя играет именно оно. Числа меняются ролями каждый шаг: остаток одного шага становится делителем следующего, а прежний делитель — делимым. Когда остаток доходит до нуля, ответом оказывается делитель того шага, то есть b последней строки, — для 1 071 и 462 это 21 из строки 147 = 7 * 21 + 0. Отдельно пересчитывать ответ не нужно: он берётся прямо из цикла, и именно поэтому напечатанные шаги и строка ответа не могут разойтись.

Что значит, если наибольший общий делитель равен единице?

Это полноценный ответ, а не отказ: числа взаимно простые, то есть общих делителей, кроме единицы, у них нет. Так выходит у 9 и 20 — алгоритм проходит три шага и доходит до 1. Практически это значит, что дробь 9/20 уже несократима, и заодно что такие пары встречаются тем чаще, чем больше числа, — на этом свойстве и держится построение обратного элемента по модулю в криптографии.

Почему нельзя ввести ноль или отрицательное число?

Потому что напечатанные шаги предполагают, что оба числа не меньше единицы. Наибольший общий делитель a и 0 равен a, и это законный ответ, но первый шаг выглядел бы как a = q * 0 + r, а такого q не существует: на ноль делить нельзя. С отрицательными та же беда — понадобилось бы правило о знаке частного и остатка, которого эта страница нигде не формулирует. Вместо того чтобы печатать процесс с дырой, страница отклоняет такой ввод.

При каком вводе шагов будет больше всего?

Наибольшее число шагов для своего размера дают соседние числа Фибоначчи: каждое частное у них равно единице, и числа почти не убывают. Пара 610 и 377 идёт тринадцать шагов, хотя числа всего трёхзначные. Размер чисел тут ни при чём: 1 000 000 и 999 998 заканчиваются за два шага, потому что остаток на втором шаге сразу нулевой. Этот результат называется теоремой Ламе, и в таблице выше число шагов вынесено в отдельный столбец именно для того, чтобы это было видно.

Чем этот алгоритм лучше разложения на множители?

Ценой. Чтобы найти делители числа перебором, нужно пробовать делители до квадратного корня из него, а алгоритм Евклида только делит число на то, которое уже держит в руках, и с каждым шагом числа быстро падают. Для 1 071 и 462 разложение потребовало бы проверок до 32, а алгоритм уложился в три шага — и при этом ни разу не ответил на вопрос, из каких множителей состоят эти числа. Отсюда и практическое правило: если нужен только общий делитель, раскладывать на множители не надо.

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)