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

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

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

${\displaystyle ay\equiv x{\pmod {m}}}$

и

${\displaystyle |x|<X,\quad 0<y<Y.}$

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

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

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

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

${\displaystyle 2a+1\equiv -a+2\equiv 0{\pmod {5}}}$.

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

${\displaystyle 2XY<m,}$

и

${\displaystyle ay_{1}-x_{1}\equiv ay_{2}-x_{2}\equiv 0{\pmod {m}}}$,

с

${\displaystyle \left|x_{1}\right|<X,\quad \left|y_{1}\right|<Y,}$

и

${\displaystyle \left|x_{2}\right|<X,\quad \left|y_{2}\right|<Y,}$

тогда

${\displaystyle {\frac {x_{1}}{y_{1}}}={\frac {x_{2}}{y_{2}}}.}$

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

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

${\displaystyle y_{2}x_{1}-y_{1}x_{2}\equiv 0{\pmod {m}}.}$

Гипотезы предполагают, что каждый член имеет абсолютное значение ниже, чем XY < м/2, а значит, абсолютная величина их разности меньше, чем м. Отсюда следует, что ${\displaystyle y_{2}x_{1}-y_{1}x_{2}=0}$, а значит, и результат.

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

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

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

${\displaystyle t_{i}m+y_{i}a=x_{i}\quad {\text{for }}i=0,1,...,}$

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

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

• Аппроксимация Паде, аналогичная теория, для аппроксимации Серия Тейлор к рациональные функции

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

• Шуп, Виктор (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