Лемма Туэ

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

Точнее, для каждой пары целых чисел $(a, m)$ с $m > 1$ , для данных двух натуральных чисел $X$ и $Y$ таких, что $X ⩽ m < XY$ , существуют два целых числа $x$ и $y$ такие, что

ay\equiv x{\pmod {m}}

и

|x|<X,\quad 0<y<Y.

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

Первое известное доказательство приписывается Акселю Туэ ( 1902 ). ^{[ 2 ]} который использовал аргумент «ячейка» . ^{[ 3 ]} Его можно использовать для доказательства теоремы Ферма о суммах двух квадратов , взяв m в качестве простого числа p , конгруэнтного 1 по модулю 4, и приняв a для удовлетворения a ² + 1 ≡ 0 мод п . (Такое « а » гарантировано для « р » теоремой Вильсона . ^{[ 4 ]})

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

В общем случае решение, существование которого утверждается леммой Туэ, не является единственным. Например, когда $a = 1$ , обычно существует несколько решений $(x, y) = (1, 1), (2, 2), (3, 3), ...$ при условии, что $X$ и $Y$ не слишком малы. Поэтому остается только надеяться на единственность рационального числа $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ x / y ⁠$ , которому $a$ конгруэнтно по модулю $m,$ если y и m просты взаимно . Тем не менее, это рациональное число не обязательно должно быть уникальным; например, если $m = 5$ , $a = 2$ и $X = Y = 3$ , есть два решения

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

.

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

2XY<m,

и

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

,

с

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

и

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

затем

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

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

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

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

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

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

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

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

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

где $x i$ неотрицательны и строго убывают. Искомое решение — это с точностью до знака первая пара $(x i, y i)$ такая, что $x i < X$ .

См. также

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

Ссылки

^ Шуп, Виктор (2005). Вычислительное введение в теорию чисел и алгебру (PDF) . Издательство Кембриджского университета . Проверено 26 февраля 2016 г. Теорема 2.33.
^ Туэ, А. (1902). «Несколько советов по теоретико-числовому методу». Кра. Научный. Компания. Пред . 7 : 57–75.
^ Айгнер, Мартин ; Циглер, Гюнтер М. (2018). Доказательства из КНИГИ (6-е изд.). Спрингер. п. 21. дои : 10.1007/978-3-662-57265-8 . ISBN 978-3-662-57265-8 .
^ Оре, Эйстейн (1948). Теория чисел и ее история . стр. 262–263.
^ Шуп 2005 , Раздел 4.6.
^ Шуп 2005 , Раздел 4.5.

[1] Шуп, Виктор (2005). Вычислительное введение в теорию чисел и алгебру (PDF) . Издательство Кембриджского университета . Проверено 26 февраля 2016 г. Теорема 2.33.

[2] Туэ, А. (1902). «Несколько советов по теоретико-числовому методу». Кра. Научный. Компания. Пред . 7 : 57–75.

[3] Айгнер, Мартин ; Циглер, Гюнтер М. (2018). Доказательства из КНИГИ (6-е изд.). Спрингер. п. 21. дои : 10.1007/978-3-662-57265-8 . ISBN 978-3-662-57265-8 .

[4] Оре, Эйстейн (1948). Теория чисел и ее история . стр. 262–263.

[FOOTNOTEShoup2005Section_4.6-5] Шуп 2005 , Раздел 4.6.

[FOOTNOTEShoup2005Section_4.5-6] Шуп 2005 , Раздел 4.5.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]