Лемма Туэ

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

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

${\ Displaystyle ау \ эквив х {\ pmod {м}}}$

а также

${\ Displaystyle | х | lt;X, \ quad 0 lt;y lt;Y.}$

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

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

СОДЕРЖАНИЕ

• 1 Уникальность
• 2 Вычислительные решения
• 3 См. Также
• 4 ссылки

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

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

${\ Displaystyle 2а + 1 \ эквив-а + 2 \ эквив 0 {\ pmod {5}}}$.

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

${\ displaystyle 2XY lt;m,}$

а также

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

с участием

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

а также

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

тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

• Шуп, Виктор (2005). Вычислительное введение в теорию чисел и алгебру (PDF). Издательство Кембриджского университета. Проверено 26 февраля +2016. CS1 maint: обескураженный параметр ( ссылка )