Математика · объяснение и практика

Как алгоритм Евклида сохраняет общий делитель

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

Синяя и оранжевая половины складываются в целый круг.

В теме Делимость, простые числа, НОД и НОК · Учебная карта

Главная мысль

Алгоритм Евклида заменяет пару положительных целых чисел парой «меньшее число и остаток от деления». Общие делители при такой замене не меняются. Когда остаток становится нулём, предыдущий ненулевой остаток является искомым наибольшим общим делителем.

Что сохраняет замена пары чисел

Возьмём двести пятьдесят два и сто девяносто восемь. При делении первого числа на второе получается остаток пятьдесят четыре. Любое число, делящее исходные два числа, делит и их разность, то есть этот остаток. Поэтому общий делитель не потеряется, если вместо большой пары рассматривать сто девяносто восемь и пятьдесят четыре.

Работает и обратное рассуждение. Если число делит меньшее исходное число и остаток, оно делит сумму остатка с нужным кратным этого меньшего числа. Такая сумма как раз восстанавливает большее исходное число. Значит, набор общих делителей в обеих парах одинаков. Сохраняется не только один удачно найденный делитель, но и сам вопрос о наибольшем из них.

Как довести вычисление до остановки

Делим сто девяносто восемь на пятьдесят четыре. Три полных раза дают сто шестьдесят два, остаток равен тридцати шести. Затем пятьдесят четыре делим на тридцать шесть и получаем восемнадцать. Последнее деление тридцати шести на восемнадцать выполняется без остатка. Предыдущий ненулевой остаток, восемнадцать, и есть НОД исходной пары.

Не выбирайте ноль как ответ только потому, что он появился в последней строке. Нулевой остаток сообщает, что последнее деление завершилось точно и дальнейшая замена уже не нужна. Искомый делитель находится в предыдущей позиции алгоритма. Для аккуратной записи удобно делать каждую строку в форме «делимое равно делитель, умноженный на частное, плюс остаток».

Пример

252 = 198 + 54; 198 = 54 × 3 + 36; 54 = 36 + 18; 36 = 18 × 2.

Последний ненулевой остаток равен восемнадцати. Проверка: 252 : 18 = 14, а 198 : 18 = 11.

Почему алгоритм завершится и когда его менять

В каждой новой паре положительный остаток меньше предыдущего делителя. Последовательность не может бесконечно уменьшаться среди неотрицательных целых чисел. Рано или поздно появится нулевой остаток. Это объясняет завершение алгоритма без предположения о каких-то удачных свойствах выбранного примера. Для положительных целых чисел процесс всегда имеет конечное число шагов.

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

Алгоритм особенно удобен, когда простое разложение чисел неизвестно. Он позволяет находить НОД через обычное деление с остатком, не перебирая все возможные множители. После нахождения делителя всё равно полезно проверить делимость обоих исходных чисел: такая проверка обнаруживает арифметическую ошибку в одной из строк.

От чтения к действию

А теперь — вы

При алгоритме Евклида последними получены остатки четырнадцать, семь и ноль. Чему равен НОД?

Частые вопросы

Всегда ли можно начать с меньшего числа?

Можно, но обычно удобнее сначала разделить большее на меньшее. При обратном порядке первое частное будет нулём, а следующая пара всё равно поменяет порядок.

Нужно ли раскладывать оба числа на простые множители?

Нет. Алгоритм Евклида использует остатки и сохраняет общие делители, поэтому предварительное разложение ему не требуется.

Углублённый разбор

Числа Фибоначчи и худший случай алгоритма Евклида

Долгая цепочка остатков требует достаточно больших исходных чисел. Обратное чтение алгоритма Евклида даёт точную нижнюю границу через числа Фибоначчи и позволяет сертифицировать худший случай в ограниченном диапазоне.

Перед началом: Деление с остатком; Числа Фибоначчи.

Сначала определите, что считается шагом

Пусть a>b>0. Считаем каждое целочисленное деление, включая последнее, в котором остаток становится нулём. Обозначим число таких делений k. При другом соглашении ответ сдвигается на единицу, поэтому число итераций нельзя сравнивать без определения счётчика. Здесь пара(2,1) требует одного шага.

Запишем a=r₀,b=r₁ и rᵢ₋₁=qᵢrᵢ+rᵢ₊₁. Все частные положительны, ненулевые остатки строго убывают. В последнем равенстве rₖ₋₁=qₖrₖ частное не меньше двух, поскольку предпоследний остаток строго больше последнего. Именно это усиление задаёт правильное начало обратной оценки.

Минимальные предшественники строятся снизу

Последний ненулевой остаток не меньше 1, предыдущий не меньше 2. Каждый более ранний остаток не меньше суммы следующих двух: частное перед ним хотя бы единица. Поэтому обратная минимальная цепочка имеет вид 1,2,3,5,8,… . При F₁=F₂=1 получаем b≥Fₖ₊₁ и a≥Fₖ₊₂.

Равенство достигается на соседних числах Фибоначчи: все промежуточные частные равны единице, а последнее равно двум. Увеличение какого-либо частного либо общего масштаба не уменьшит необходимые исходные числа. Это объясняет, почему большие частные обычно сокращают число делений, хотя одно такое деление может быть вычислительно дороже.

Граница числа делений не является временем программы

Если a ограничено сверху, достаточно найти первое число Фибоначчи, превышающее этот предел. Следующая длина цепочки уже невозможна. Для доказательства достижимости нужно предъявить допустимую пару и выписать все остатки, а не только сослаться на асимптотическую логарифмическую оценку.

Утверждение относится к количеству делений произвольной точности. Оно не говорит, что каждый шаг занимает одинаковое машинное время. Для длинных целых важны размеры делимого и делителя, алгоритм деления и представление чисел. Последовательные вычитания также имеют другой счётчик и другую худшую ситуацию.

Максимальная длина ниже ста

Условие. Найдите наибольшее число делений алгоритма Евклида среди целых 1≤b<a≤100. Последнее деление с нулевым остатком учитывается.

  1. Если потребовалось бы 10 делений, то a≥F₁₂=144. Это выходит за допустимый диапазон, значит k≤9.
  2. Пара a=89,b=55 допустима. Первые остатки равны 34,21,13,8,5.
  3. Далее получаем 3,2,1,0. Полный список новых остатков содержит девять значений, последнее нулевое.
  4. Все частные до последнего равны 1, последнее равно 2. Пара достигает верхней границы и сертифицирует максимум.

Ответ. Максимум равен 9 делениям; его достигает пара(89,55).

Проверка. Независимый перебор всех 4950 пар b<a≤100 даёт максимум 9. Обратная граница F₁₂=144 доказывает невозможность десяти шагов без доверия к перебору.

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

Проверьте понимание

Сколько делений максимально возможно при 1≤b<a≤100 по принятому счётчику?

Вопросы к этой главе

Большое первое частное создаёт худший случай?

Обычно оно сразу резко уменьшает остаток. Максимальная длина при ограничении величины входов возникает при минимально возможных частных, а не при большом первом частном.

Общий делитель должен быть единицей?

Для самой нижней границы это не требуется. Но общий множитель масштабирует всю цепочку, поэтому самые маленькие входы для заданного числа делений имеют НОД 1.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Victor Shoup: A Computational Introduction to Number Theory and Algebra, §4.1

    Вебом прочитаны теорема 4.1 и её условия: положительные убывающие остатки, последняя операция деления, логарифмическая оценка. Точная индексация чисел Фибоначчи и ограниченный перебор главы выведены отдельно.

Бинарный алгоритм Штейна: НОД без деления

НОД можно вычислять без целочисленного деления: выделять степени двойки, сравнивать нечётные остатки и вычитать меньший из большего. Для корректности нужно отдельно хранить только общий вынесенный множитель.

Перед началом: Чётность; Общие делители.

Три тождества заменяют деление

Для неотрицательных целых НОД(2u,2v)=2 НОД(u,v). Если u нечётно, то НОД(u,2v)=НОД(u,v): общий делитель не содержит двойку. Наконец, вычитание сохраняет общие делители: НОД(u,v)=НОД(u,v−u). Последнее равенство применяют после упорядочивания положительных аргументов.

Сначала вынесем 2ᵏ, где k — минимум показателей двойки в двух ненулевых входах. Затем уберём оставшиеся двойки из каждого рабочего операнда. Они уже не являются общими, потому что после общего выноса хотя бы один аргумент нечётен. Рабочая пара теперь состоит из нечётных чисел, а сохранённый коэффициент 2ᵏ остаётся отдельно.

После вычитания снова убирайте двойки

Если нечётные u<v, заменим v на v−u. Разность положительна и чётна; удаление всех её множителей двойки сохраняет НОД с нечётным u. Снова сравним пару и продолжим. При равенстве u=v найден рабочий НОД. Результат умножается на исходный сохранённый общий множитель.

Терминация следует из строгого уменьшения суммы положительных рабочих операндов на каждом вычитании; сдвиги её тоже уменьшают. Инвариант формулируется точно: исходный НОД равен 2ᵏ НОД(u,v). Удалённая из одного операнда двойка после начала цикла не должна дополнительно попадать в общий коэффициент.

Нулевые входы и стоимость требуют отдельного договора

Для пары(a,0) ответом служит |a|; обработка должна произойти до подсчёта младших нулевых битов, поскольку для нуля такой показатель не конечен. Знаки входов снимают в начале. Для пары(0,0) математические соглашения различаются; программная библиотека может отдельно определить результат 0.

Сдвиг и вычитание удобны для двоичного представления, однако отсутствие деления само по себе не доказывает превосходства на любой платформе. Нужно учитывать размер целых, реализацию поиска младшего единичного бита и накладные расходы. Сравнивать только количество строчек трассы с числом делений Евклида некорректно: это разные операции.

Общая двойка и две нечётные разности

Условие. Вычислите НОД(84,66) бинарным методом, явно отделяя общий множитель от двойки, удаляемой только из одного рабочего числа.

  1. Оба входа чётны: выносим общий множитель 2. Остаётся(42,33); из 42 удаляем ещё одну двойку и получаем нечётную пару(21,33).
  2. Разность 33−21=12. Удаляем из 12 две двойки и получаем пару(21,3); общий внешний коэффициент по-прежнему 2.
  3. Разность 21−3=18. Удаляем одну двойку, получая пару(9,3). Затем 9−3=6, после сдвига остаётся(3,3).
  4. Рабочий НОД равен 3, исходный равен 2·3=6. Ни одна отдельная чётная разность не увеличивала общий вынесенный коэффициент.

Ответ. НОД(84,66)=6.

Проверка. Число 6 делит оба входа. Тождество 4·84−5·66=6 показывает, что любой общий делитель делит 6, независимо от выполненной двоичной трассы.

Где легко ошибиться. Сохранённый показатель двойки меняется только при общем начальном выделении. Удаление двойки из одного операнда рядом с нечётным партнёром не добавляет общего множителя.

Проверьте понимание

Какой общий множитель сохраняется снаружи во всей трассе?

Вопросы к этой главе

Можно заменить сдвиги обычным делением на два?

Математически да: деление всегда точное. Бинарным метод называют из-за выбора операций и представления, а не из-за иного определения НОД.

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

Перед вычитанием оба рабочих операнда сделаны нечётными. Разность двух нечётных чётна; при равных операндах нужно завершиться, а не пытаться удалять двойки из нуля.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • GNU MP: Binary GCD, §15.3.1

    Первичная документация разработчиков GMP: прочитаны вычитание нечётных операндов, удаление множителей 2 и пределы сравнения реализаций. Собственная трасса и доказательство инварианта не повторяют пример источника.

Переносы в основании p определяют делимость биномиального коэффициента

Показатель простого в биномиальном коэффициенте можно узнать по переносам цифр, не вычисляя сам огромный коэффициент. Теорема Куммера связывает локальную школьную операцию сложения с точной делимостью на степень простого. Важны все переносы, включая цепочку, запущенную одним младшим разрядом.

Перед началом: Позиционная запись числа; Биномиальный коэффициент.

Сначала считаем простые множители факториала

Обозначим vₚ(N) показатель простого p в положительном целом N. Для факториала vₚ(n!)=Σⱼ≥1 floor(n/pʲ): кратные p дают первый множитель, кратные p² — ещё один и так далее. Поэтому для 0≤k≤n показатель в C(n,k) равен разности трёх таких сумм. Сумма конечна, поскольку при pʲ>n все её слагаемые нулевые.

Если sₚ(n) — сумма цифр записи n в основании p, формула Лежандра также даёт vₚ(n!)=(n−sₚ(n))/(p−1). Вычитая выражения для k! и (n−k)!, получаем vₚ(C(n,k))=(sₚ(k)+sₚ(n−k)−sₚ(n))/(p−1). Исчезновение самих больших чисел показывает, почему одних цифр достаточно для точного ответа.

Каждый перенос уменьшает сумму цифр на p−1

Сложим k и n−k в основании p. При переносе p единиц одного разряда заменяются одной единицей следующего. Сумма цифр уменьшается на p−1. Учитывая все разряды и входящие переносы, общий дефицит суммы цифр равен (p−1) умножить на число переносов. Сравнение с предыдущей формулой доказывает теорему Куммера.

В каждом разряде складываются две цифры не больше p−1 и перенос 0 либо 1, поэтому новый перенос также равен 0 либо 1. Но один исходный перенос может вызвать следующий даже там, где две собственные цифры дают только p−1. Нельзя считать лишь позиции, где сумма двух записанных цифр сама не меньше p: требуется настоящий пошаговый алгоритм сложения.

Нулевой показатель и границы тоже имеют смысл

Если переносов нет, коэффициент не делится на p. Это не означает, что он прост или равен единице; другие простые могут делить его сколько угодно раз. При k=0 или k=n коэффициент равен 1, и переносов действительно нет. Теорема требует простого основания: запись в составном основании не измеряет показатель единственного простого множителя. Для большого коэффициента процедура работает по числу цифр, а не по его величине.

Три переноса, запущенные младшими цифрами

Условие. Найдите v₃(C(28,11)) по сложению 11 и 17 в троичной системе, не вычисляя биномиальный коэффициент до получения показателя.

  1. Имеем 11=(102)₃, 17=(122)₃, 28=(1001)₃. Складываем справа налево.
  2. В единицах 2+2=4: пишем 1, переносим 1. В следующем разряде 0+2+1=3: пишем 0, снова переносим 1.
  3. В старшем исходном разряде 1+1+1=3: пишем 0, переносим 1 в новый разряд. Всего произошло три переноса, поэтому показатель равен 3.
  4. Независимо суммы цифр равны 3,5 и 2. Разность (3+5−2)/(3−1)=3 совпадает. Только после этого вычисление C(28,11)=21474180 показывает делимость на 27 и неделимость на 81.

Ответ. v₃(C(28,11))=3: число делится на 3³, но не на 3⁴.

Проверка. Отдельная факториальная сумма даёт v₃(28!)=13, v₃(11!)=4, v₃(17!)=6, разность 3. Прямой целый коэффициент после деления на 27 равен 795340 и не делится на 3.

Где легко ошибиться. Не игнорируйте перенос из предыдущего разряда. В примере второй перенос возник из 0+2+1, хотя сумма двух исходных цифр 0+2 меньше основания.

Проверьте понимание

Наибольшая степень 3, делящая C(28,11), равна…

Вопросы к этой главе

Почему считаются переносы при k+(n−k), а не n+k?

Именно эти два слагаемых входят в знаменатель n!/(k!(n−k)!). Их сумма равна n, поэтому дефицит сумм цифр совпадает с показателем биномиального коэффициента.

Можно ли получить весь остаток коэффициента по p⁴?

Количество переносов задаёт только степень делимости. Оно не определяет оставшуюся единичную часть коэффициента и потому само по себе не восстанавливает полный остаток по более высокой степени простого.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Tamás Lengyel: On divisibility properties…, §3

    Прочитаны Theorems3.1–3.2: переносы Куммера и формула Лежандра через сумму цифр. Другие результаты статьи про числа Моцкина не используются. Собственное C(28,11) проверено целочисленно. Попытка открыть Wilf dm36.pdf дала 403 и не считается чтением.

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

В кольце гауссовых целых a+bi алгоритм Евклида сохраняет общие делители, но остаток измеряется квадратом комплексной длины. Правильное округление обеих координат частного обеспечивает уменьшение нормы. Итоговый НОД определён с точностью до четырёх единиц, а не положительным знаком.

Перед началом: Комплексное деление; Обычный алгоритм Евклида.

Норма заменяет порядок на прямой

Для z=a+bi с целыми a,b положим N(z)=a²+b². Норма мультипликативна: N(zw)=N(z)N(w). При ненулевом z она является положительным целым. Поэтому последовательность ненулевых остатков со строго убывающими нормами обязательно закончится. Сравнение действительных частей такого свойства не даёт: комплексные числа не имеют подходящего линейного порядка для обычного условия 0≤r<b.

Для деления α на β≠0 вычислим α/β=x+yi рационально, затем округлим x и y до ближайших целых u,v. Берём q=u+vi и r=α−qβ. Тогда N(r)/N(β)=(x−u)²+(y−v)²≤1/2, откуда N(r)<N(β). При половинных координатах возможен выбор; любой ближайший вариант сохраняет оценку.

Сохранение делителей даёт и НОД, и сертификат

Равенство α=qβ+r показывает: общий делитель α,β делит r, а общий делитель β,r делит α. Поэтому можно заменять пару на (β,r). Последний ненулевой остаток делит исходные числа, и каждый их общий делитель делит этот остаток. Именно это свойство определяет НОД по делимости, независимо от внешнего вида комплексного числа.

Обратная подстановка выражает найденный НОД как uα+vβ с гауссовыми целыми u,v. Такой сертификат Безу вместе с проверкой делимости является коротким независимым свидетельством. Норма НОД сама по себе недостаточна: разные неассоциированные числа могут иметь одну норму и делить разные входы. Нужно проверять комплексные произведения либо точные частные.

Неоднозначность ограничена обратимыми множителями

Единицы Z[i] равны 1,−1,i,−i, поскольку только они имеют норму 1. Поэтому δ и iδ являются равноправными НОД. Можно выбрать удобное соглашение о квадранте, но оно не является математическим свойством исходной пары. Округление всегда вниз вместо ближайшего может дать сумму квадратов ошибок больше единицы и нарушить строгое уменьшение нормы; привычку от целочисленного деления здесь переносить нельзя.

Комплексный остаток и одношаговый Безу

Условие. Найдите гауссов НОД α=13+9i и β=5+i, укажите остатки и сертификат Безу.

  1. Делим точно: α/β=(13+9i)(5−i)/26=(74+32i)/26=37/13+(16/13)i. Ближайшее гауссово целое равно q=3+i.
  2. Вычисляем r=α−(3+i)β=−1+i. Его норма равна 2, тогда как N(β)=26, поэтому уменьшение строгое.
  3. Следующее деление точное: β/(−1+i)=−2−3i. Остаток нулевой, последний ненулевой r является НОД.
  4. Сертификат сразу виден из первого шага: δ=α−(3+i)β=−1+i. Отдельно α/δ=−2−11i и β/δ=−2−3i лежат в Z[i].

Ответ. Один НОД равен −1+i; все НОД получаются умножением на ±1,±i.

Проверка. Прямые произведения δ(−2−11i)=13+9i и δ(−2−3i)=5+i проверяют делимость. Линейная комбинация δ=α−(3+i)β показывает, что любой общий делитель обязан делить δ.

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

Проверьте понимание

Какой из предложенных гауссовых целых является НОД указанной пары?

Вопросы к этой главе

Почему остаток может иметь отрицательную действительную часть?

Остаток ограничен нормой, а не порядком на вещественной оси. Число −1+i вполне допустимо и имеет маленькую норму. Никакой дополнительной коррекции до неотрицательной части алгоритм не требует.

Почему 1−i тоже правильный ответ?

Он равен −δ, а −1 является единицей. Делимость и множество общих делителей сохраняются. В отличие от обычных целых здесь нет естественного требования выбрать именно положительный НОД.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Keith Conrad: Gaussian Integers, §3–4

    Прочитаны Theorem3.1 с оценкой N(r)≤N(b)/2 и Theorem4.3 о последнем ненулевом остатке. Числа 13+9i и 5+i и сертификат Безу созданы отдельно; округление выполнено рационально.

Цепные дроби и наилучшее приближение с ограниченным знаменателем

Подходящие дроби полезны не только как хорошие численные приближения. Определитель соседней пары равен единице по модулю и даёт запрет на малые знаменатели между ними. Вместе с точной локализацией исходного числа это превращает поиск близкой дроби в проверяемый сертификат оптимальности.

Перед началом: Алгоритм Евклида и цепная дробь; Сравнение рациональных чисел.

Соседние подходящие дроби образуют целочисленный базис

Для простой цепной дроби числители и знаменатели удовлетворяют p_n=a_np_(n−1)+p_(n−2), q_n=a_nq_(n−1)+q_(n−2). Из этой рекурсии следует p_nq_(n−1)−p_(n−1)q_n=(−1)^(n−1). В частности, соседние дроби несократимы и их целочисленные столбцы образуют унимодулярный базис плоскости.

Если a/b<c/d и bc−ad=1 при положительных знаменателях, всякая рациональная дробь r/s строго между ними имеет s≥b+d. Действительно, целые положительные числа rb−as и cs−rd дают тождество s=d(rb−as)+b(cs−rd). Оба слагаемых не меньше соответствующих знаменателей. Это точный запрет, не требующий десятичных приближений.

Вид ошибки и граница знаменателя задаются явно

Приближение первого рода минимизирует |α−p/q|, второго рода — |qα−p|. Эти постановки связаны, но не совпадают при сравнении разных знаменателей. Для произвольного ограничения q≤N одного списка подходящих дробей может быть мало: промежуточные дроби также способны стать оптимальными.

В малом примере удобно использовать соседнюю пару, заключающую α, и проверить, какая граница ближе. Если между ними запрещены все рассматриваемые знаменатели, остаётся исключить дроби снаружи интервала: они не могут быть ближе соответствующей границы. Так получается самостоятельное доказательство оптимальности конкретного ответа, без чрезмерного общего утверждения о любом N.

Сравнение с иррациональным числом можно провести точно

Для положительного квадратного корня неравенства с положительными рациональными числами проверяются возведением в квадрат. Чтобы сравнить расстояния до двух границ, достаточно сравнить α с их серединой. Если середина находится справа от α, левая граница ближе; если слева — правая.

Соседний определитель также показывает ширину интервала: c/d−a/b=1/(bd). Он объясняет, почему растущие знаменатели дают всё более тесное заключение. Но малая ширина сама по себе ещё не указывает лучшую сторону. Важно отдельно проверить положение α и соблюдать ограничение на допустимый знаменатель в итоговом ответе.

Лучшее приближение к √5 при знаменателе не больше семнадцати

Условие. Найдите ближайшую к √5 рациональную дробь p/q при 1≤q≤17. Используйте подходящие дроби и докажите оптимальность, а не только малую ошибку найденного кандидата.

  1. Цепная дробь √5=[2;4,4,4,…] даёт дроби 2/1, 9/4, 38/17. Последняя меньше √5, поскольку 38²=1444<5·17²=1445; 9/4 больше √5.
  2. Для границ 38/17 и 9/4 имеем 9·17−38·4=1. Значит, любая дробь строго между ними имеет знаменатель не меньше 17+4=21.
  3. Середина границ равна 305/136. Её квадрат больше пяти, поскольку 305²=93025>5·136²=92480. Следовательно, √5 находится левее середины и ближе к 38/17.
  4. При знаменателе не больше 17 внутренняя дробь невозможна. Внешняя слева не ближе 38/17, внешняя справа не ближе 9/4, которая уже хуже. Поэтому 38/17 является единственным ближайшим рациональным значением.
  5. Следующая подходящая дробь 161/72 ещё точнее, но нарушает ограничение. Проверка допустимости исключает её независимо от величины ошибки.

Ответ. Ближайшая дробь равна 38/17. Соседний определитель запрещает конкурента между границами с q≤17, а сравнение с серединой выбирает правильную границу.

Проверка. Ограниченный перебор всех q от 1 до 17 и ближайших целых числителей независимо подтверждает ответ. В основном доказательстве используются только целочисленные определители и сравнения квадратов.

Где легко ошибиться. Не называйте любой конвергент лучшим ответом при произвольной верхней границе знаменателя без проверки промежуточных дробей. Здесь оптимальность подтверждена отдельным запретом через соседнюю пару.

Проверьте понимание

Какая дробь ближе всего к √5 среди рациональных чисел со знаменателем от 1 до 17?

Вопросы к этой главе

Можно ли использовать сокращённую запись той же дроби как нового конкурента?

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

Почему более точная дробь 161/72 не подходит?

Постановка ограничивает знаменатель числом 17. Качество приближения проверяется только после допустимости; маленькая ошибка не компенсирует нарушение этого ограничения.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • P. Guerzhoy: A short introduction to continued fractions

    Прочитаны рекурсии конвергентов и раздел о различии лучших приближений первого и второго рода. Конкретный сертификат для √5 и знаменателей до 17 выведен через соседний определитель; примеры источника не воспроизводятся.

Лемма Бёрнсайда считает слова с точностью до поворота

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

Перед началом: Орбита и стабилизатор действия конечной группы; Циклический сдвиг и НОД двух целых чисел.

Каждая орбита вносит один полный размер группы

Конечные бинарные слова фиксированной длины и веса; отождествляются только циклические повороты, без отражений и перестановки цветов.

Пусть конечная группа G переставляет конечное множество X. Посчитаем пары (g,w), для которых g оставляет w на месте. Суммирование сначала по преобразованиям даёт Σ_g|Fix(g)|. Суммирование по словам даёт Σ_w|Stab(w)|. Внутри каждой орбиты размер стабилизатора одинаков и равен |G|, делённому на размер орбиты.

Поэтому любая орбита, большая или маленькая, вносит в последнюю сумму ровно |G|. Число орбит равно среднему количеству неподвижных объектов: (1/|G|)Σ_g|Fix(g)|. Делят не общее число объектов на |G|, а сумму неподвижных количеств. Это различие как раз компенсирует короткие периодические орбиты.

НОД определяет циклы поворота позиций

Сдвиг на k позиций в слове длины n разбивает позиции на d=gcd(n,k) циклов, каждый длины L=n/d. Слово неподвижно тогда и только тогда, когда все позиции одного такого цикла имеют одинаковый символ. Для произвольного алфавита из q букв это даёт qᵈ неподвижных слов, поскольку выборы на разных циклах независимы.

Если дополнительно задано ровно m единиц, возникает условие L|m. Один выбранный единичный цикл сразу занимает L позиций. При делимости надо выбрать m/L циклов из d, поэтому неподвижных слов C(d,m/L); без делимости их ноль. Для тождественного сдвига k=0 имеем d=n,L=1, что возвращает обычное C(n,m).

Разрешённая группа является частью условия

Ожерелье без отмеченного начала соответствует орбите циклической группы. Если разрешить ещё переворот, появляется диэдральная группа и другие неподвижные конфигурации. Нельзя сначала посчитать повороты, а затем автоматически разделить ответ на два: некоторые круговые слова совпадают со своим отражением с точностью до поворота.

Также надо различать подсчёт орбит и выбор канонического представителя. Минимальный лексикографический поворот помогает перечислить классы на малом примере, но лемма не требует строить представителей. Слова с коротким периодом входят в задачу наравне с непериодическими; исключение таких слов привело бы к другой формуле и другому множеству объектов.

Восемь позиций с четырьмя единицами

Условие. Сколько бинарных круговых слов длины 8 с ровно четырьмя единицами различно с точностью до поворота? Отражения не отождествляются.

  1. Всего помеченных слов C(8,4)=70. Группа состоит из восьми сдвигов k=0,…,7; простой ответ 70/8 нецелый и уже показывает неодинаковые размеры орбит.
  2. Для k=0 неподвижны все 70 слов. Для нечётных k число d=1, длина единственного цикла 8 не делит вес 4, поэтому неподвижных слов нет.
  3. При k=2 и k=6 имеем d=2,L=4: выбираем один единичный цикл из двух, то есть по 2 слова. При k=4 имеем d=4,L=2 и C(4,2)=6 слов.
  4. Сумма неподвижных количеств равна 70+2+2+6=80. После деления на 8 получаем 10 круговых слов. Все восемь групповых элементов учтены, включая тождественный.

Ответ. Получается 10 орбит относительно поворотов. Число 70 относится к словам с отмеченным началом.

Проверка. Прямое перечисление орбит даёт одну орбиту размера 2, одну размера 4 и восемь размера 8. Они содержат 2+4+8·8=70 слов, а всего орбит 1+1+8=10.

Где легко ошибиться. Повороты и отражения задают разные отношения эквивалентности. Уточняйте группу до подсчёта, а не после получения численного ответа.

Проверьте понимание

Сколько орбит поворотов получается в разобранном примере длины 8 и веса 4, без отражений?

Вопросы к этой главе

Почему сдвиг на одну позицию не фиксирует здесь ни одного слова?

Он объединяет все восемь позиций в один цикл. Неподвижное слово должно состоять целиком из нулей или единиц; ни одно не имеет веса четыре.

Как выглядит короткая орбита размера два?

Это два слова 01010101 и 10101010. Чётные повороты оставляют каждый из них на месте, поэтому восемь групповых элементов не создают восемь разных слов.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Ben Lynn, Stanford — Polya Theory: Burnside’s Lemma

    Двойной подсчёт неподвижных пар и усреднение по группе. Наша задача ограничивает вес и использует только повороты; формула через длины циклов и перебор восьми позиций получены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться