У модульній арифметиці, лема Туе стверджує, що будь-яке модульне ціле число можна подати як модульний дріб, так, що чисельник та знаменник мають абсолютні значення, не більші за квадратний корінь з модуля.
Точніше кажучи, для кожної пари цілих чисел , де , заданих двома натуральними числами та , такими, що , існує два цілих числа та , такі, що
та
Зазвичай та дорівнюють найменшому натуральному числу, більшому за квадратний корінь з , проте загальна форма іноді корисна і спрощує формулювання теореми єдиності (нижче). Theorem 2.33.
Перше відоме доведення приписують (1902) , який використав принцип Діріхле . Його можна використати, щоб довести теорему Ферма про суму двох квадратів, якщо взяти простим числом , конгруентним 1 за модулем 4, та взяти , таке, що . (Існування такого для заданого гарантується теоремою Вілсона.)
Єдиність
Загалом, розв'язок, який існує за лемою Туе, не єдиний. Наприклад, при є декілька розв'язків , за умови, що та не надто малі. Через це лишається лише сподіватися на єдиність раціонального числа , якому конгруентне за модулем , якщо та взаємно прості. Тим не менш, це раціональне число не обов'язково єдине. Наприклад, якщо , і , то буде два розв'язки .
Проте для досить малих та , якщо розв'язок існує, він єдиний. Точніше, з використанням позначень, введених вище, якщо
та , з
та
тоді .
Цей результат лежить в основі , яка дозволяє використовувати модульну арифметику для обчислення раціональних чисел, для яких відомі межі чисельників та знаменників.
Доведення досить просте: треба домножити кожну конгруентність на інший і відняти, тоді отримаємо . З гіпотез випливає, що кожен член виразу має абсолютне значення менше за , і що абсолютне значення їхньої різниці менше за . Це означає, що , а отже твердження доведено.
Обчислення розв'язків
Оригінальне доведення леми Туе не є ефективним у тому сенсі, що воно не надає жодного швидкого способу знаходження розв'язку. Натомість, розширений алгоритм Евкліда дозволяє отримати доведення, яке приводить до ефективного алгоритму з такою самою обчислювальною складністю, як і звичайний алгоритм Евкліда.
Точніше кажучи, маючи два цілі числа та , що з'являються в лемі Туе, розширений алгоритм Евкліда обчислює три послідовності цілих чисел , та , такі, що
де — невід'ємні числа, що строго спадають. Шуканий розв'язок (з точністю до знаку) — це перша пара (, для якої виконується .
Див. також
Апроксимація Паде — подібна теорія для наближення ряду Тейлора раціональними функціями. Діофантова апроксимація Теорія трансцендентних чисел Обернене за модулем число
Література