Лемма Туэ - Thues lemma - Wikipedia

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

Точнее для каждой пары целые числа (а, м) с м > 1, учитывая два натуральных числа Икс и Y такой, что Иксм < XY, есть два целых числа Икс и у такой, что

и

Обычно берется Икс и Y равно наименьшему целому числу больше квадратного корня из м, но общая форма иногда бывает полезна и упрощает формулировку теоремы единственности (ниже).[1]

Первое известное доказательство приписывается Аксель Туэ  (1902 ),[2] кто использовал голубятня аргумент.[3][4] Это может быть использовано для доказательства Теорема Ферма о суммах двух квадратов принимая м быть первым п это 1 мод 4 и беря а удовлетворить а2 + 1 = 0 мод п. (Такое «а» гарантируется для «р» Теорема Вильсона.[5])

Уникальность

Вообще говоря, решение, существование которого утверждает лемма Туэ, не единственно. Например, когда а = 1 обычно есть несколько решений (Икс,у) = (1,1), (2,2), (3,3), ..., при условии что Икс и Y не так уж и малы. Поэтому можно только надеяться на уникальность Рациональное число Икс/у, которому а конгруэнтно по модулю м если у и м взаимно просты. Тем не менее, это рациональное число не обязательно должно быть уникальным; например, если м = 5, а = 2 и Икс = Y = 3, есть два решения

.

Однако для Икс и Y достаточно мала, если решение существует, то оно уникально. Точнее, с указанными выше обозначениями, если

и

,

с

и

тогда

Этот результат является основой для рациональная реконструкция, что позволяет использовать модульную арифметику для вычисления рациональных чисел, для которых известны границы для числителей и знаменателей.[6]

Доказательство довольно просто: умножая каждое сравнение на другое уя и вычитая, получаем

Гипотезы предполагают, что каждый член имеет абсолютное значение ниже, чем XY < м/2, а значит, абсолютная величина их разности меньше, чем м. Отсюда следует, что , а значит, и результат.

Вычислительные решения

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

Точнее, учитывая два целых числа м и а фигурирующий в лемме Туэ, расширенный алгоритм Евклида вычисляет три последовательности целых чисел (тя), (Икся) и (уя) такой, что

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

Смотрите также

Рекомендации

  • Шуп, Виктор (2005). Вычислительное введение в теорию чисел и алгебру (PDF). Издательство Кембриджского университета. Получено 26 февраля 2016.
  1. ^ Шуп, теорема 2.33
  2. ^ Туэ, А. (1902), "Et par antydninger til en taltheoretisk metode", Kra. Виденск. Сельск. Для ч., 7: 57–75
  3. ^ Кларк, Пит Л. "Лемма Туэ и двоичные формы". CiteSeerX  10.1.1.151.636. Цитировать журнал требует | журнал = (помощь)
  4. ^ Лендаль, Карл (22 марта 2011 г.). «Лекция о суммах квадратов» (PDF). Получено 26 февраля 2016. Цитировать журнал требует | журнал = (помощь)
  5. ^ Оре, Ойштейн (1948), Теория чисел и ее история, стр. 262–263
  6. ^ Shoup, раздел 4.6
  7. ^ Шуп, раздел 4.5