Прыжки с места

В чисел теории прыжок Виета , также известный как переворачивание корня является методом доказательства . Чаще всего он используется для задач, в которых задана связь между двумя целыми числами, а также утверждение для доказательства ее решений. В частности, его можно использовать для получения новых решений квадратного диофантова уравнения из известных. Существует множество вариантов прыжков Виеты, все из которых связаны с общей темой бесконечного спуска путем поиска новых решений уравнения с использованием формул Виеты .

История

Прыжки Виета — классический метод теории квадратных диофантовых уравнений и бинарных квадратных форм . Например, его использовали при анализе уравнения Маркова еще в 1879 году и в статье Миллса 1953 года.

В 1988 году этот метод привлек внимание к задачам математических олимпиад в свете первой олимпиадной задачи, и его использовали в решении, которое было предложено для Международной математической олимпиады и считалось самой сложной задачей на конкурсе:

Пусть a и b — целые положительные числа такие, что ab + 1 делит a ² + б ² . Покажи это ${\frac {a^{2}+b^{2}}{ab+1}}$ представляет собой квадрат целого числа.

Артур Энгель написал следующее о сложности задачи:

Никто из шести членов австралийского проблемного комитета не смог ее решить. Двумя участниками были муж и жена Джордж и Эстер Секерес , оба известные решатели и создатели проблем. Поскольку это была задача теории чисел, ее отправили четырем самым известным австралийским теоретикам чисел. Их попросили поработать над этим шесть часов. Никто из них не смог решить эту проблему за это время. Проблемный комитет представил ее на рассмотрение жюри XXIX IMO, отмеченную двойной звездочкой, что означало сверхсложную задачу, возможно, слишком трудную для постановки. После долгого обсуждения жюри наконец набралось смелости выбрать ее последней задачей конкурса. Одиннадцать студентов дали идеальные решения.

Среди одиннадцати студентов, получивших максимальный балл за решение этой задачи, были Нго Бо Чау , Рави Вакил , Звезделина Станкова и Никушор Дан . Эмануил Атанасов (из Болгарии) решил задачу в абзаце и получил специальный приз.

прыжок

Концепция стандартного прыжка Виета представляет собой доказательство от противного и состоит из следующих четырех этапов:

1. Предположим в сторону противоречия, что существует некоторое решение ( a ₁ , a ₂ , ... ), которое нарушает данные требования.
2. Возьмем минимальное такое решение согласно некоторому определению минимальности.
3. Замените некоторое a _i на переменную x в формулах и получите уравнение, для которого a _i является решением.
4. Используя формулы Виеты, покажите, что из этого следует существование меньшего решения и, следовательно, противоречие.

Пример

Проблема №6 в IMO 1988 : Пусть a и b — положительные целые числа, такие, что ab + 1 делит a ² + б ² . Докажите, что ⁠ a ² + б ² / ab + 1 ⁠ — полный квадрат .

1. Зафиксируйте некоторое значение k , которое является неквадратным положительным целым числом. Предположим, существуют целые положительные числа ( a , b ), для которых k = ⁠ a ² + б ² / аб + 1 ⁠ .
2. Пусть ( A , B ) — целые положительные числа, для которых k = ⁠ A ² + Б ² / AB + 1 ⁠ и такой, что A + B минимизирован, и без ограничения общности предположим, что A ≥ B .
3. Исправив B , замените A на переменную x, чтобы получить x ² – ( кБ ) x + ( Б ² – к ) знак равно 0 . Мы знаем, что один корень этого уравнения равен x ₁ = A . По стандартным свойствам квадратных уравнений мы знаем, что другой корень удовлетворяет условиям x ₂ = kB – A и x ₂ = ⁠ B ² – к / А ⁠ .
4. Первое выражение для x ₂ показывает, что x ₂ является целым числом, а второе выражение подразумевает, что x ₂ ≠ 0, поскольку k не является полным квадратом. От ⁠ x ₂ ² + Б ² / x ₂ B + 1 ⁠ = k > 0, далее следует, что x ₂ B > −1 , и, следовательно, x ₂ является положительным целым числом. Наконец, A ≥ B означает, что x ₂ = ⁠ B ² - к / А ⁠ < ⁠ B ² / A ⁠ ≤ A , следовательно, x ₂ < A и, следовательно, 2 ₊ B < A + B , что противоречит минимальности A + B. x

спуск

Метод постоянного спуска Вьета-прыжка используется, когда мы хотим доказать утверждение о том, что константа k имеет какое-то отношение к отношению между a и b . В отличие от стандартных прыжков Виета, постоянный спуск не является доказательством от противного и состоит из следующих четырех этапов:

1. Случай равенства доказан, так что можно предположить, что a > b .
2. b и k фиксированы, а выражение, связывающее a , b и k, преобразуется в квадрат с коэффициентами, выраженными через b и k , одним из корней которого является a . Другой корень x ₂ определяется по формулам Виета.
3. Для всех ( a , b ) выше определенного базового случая покажите, что 0 < x ₂ < b < a и что x ₂ является целым числом. Таким образом, сохраняя то же значение , мы можем заменить ( a , b ) на ( b , x2 _k ) и повторять этот процесс, пока не придем к базовому случаю.
4. Докажите утверждение для базового случая, а поскольку k в ходе этого процесса оставалось постоянным, этого достаточно, чтобы доказать утверждение для всех упорядоченных пар.

Пример

Пусть a и b — целые положительные числа такие, что ab делит a ² + б ² + 1 . Докажите, что 3 ab = a ² + б ² + 1 .

1. Если а = б , а ² деление 2 а ² + 1 означает, что ² делит 1, и, следовательно, положительные целые числа a = b = 1 и 3(1)(1) = 1 ² + 1 ² + 1 . Итак, без ограничения общности, предположим, что a > b .
2. Для любого ( a , b ), удовлетворяющего данному условию, пусть k = ⁠ a ² + б ² + 1 / ab ⁠ и переставьте и замените, чтобы получить x ² - ( кб ) Икс + ( б ² + 1) = 0 . Один корень этого квадратичного уравнения равен a , поэтому по формулам Виеты другой корень можно записать следующим образом: x ₂ = kb − a = ⁠ b ² + 1 / a ⁠ .
3. Первое уравнение показывает, что x ₂ — целое число, а второе — что оно положительное. Поскольку a > b и они оба целые числа, a ≥ b + 1 и, следовательно, ab ≥ b ² + б ; Пока b > 1 , мы всегда имеем ab > b ² + 1 и, следовательно, x ₂ = ⁠ b ² + 1 / а ⁠ < б . образом, сохраняя то же самое k , мы можем заменить ( a , b ) на ( b , x2 _Таким ) и повторять этот процесс, пока не придем к базовому случаю.
4. Базовый случай, к которому мы приходим, — это случай, когда b = 1 . Чтобы ( a , 1) удовлетворяло данному условию, a должен разделить a ² + 2 , что означает, что a делит 2, образуя либо 1, либо 2. Первый случай исключается, поскольку a = b . Во втором случае k = ⁠ a ² + б ² + 1 / ab ⁠ = ⁠ 6 / 2 ⁠ знак равно 3 . Поскольку k остается постоянным на протяжении всего процесса прыжков Виеты, этого достаточно, чтобы показать, что для любого ( a , b ), удовлетворяющего данному условию, k всегда будет равно 3.

интерпретация

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

1. Из данного условия получаем уравнение семейства гипербол, которые не изменяются при перестановке x и y так, чтобы они были симметричны относительно прямой y = x .
2. Докажите требуемое утверждение для пересечений гипербол и прямой y = x .
3. Предположим, что на некоторой гиперболе существует некоторая точка решетки ( x , y ) и без ограничения общности x < y . имеется соответствующая точка решетки с такой же координатой x Тогда по формулам Виета на другой ветви гиперболы , и путем отражения через y = x получается новая точка на исходной ветви гиперболы.
4. Показано, что этот процесс создает нижние точки на той же ветви и может повторяться до тех пор, пока не будет достигнуто некоторое условие (например, x = 0 ). Тогда подстановкой этого условия в уравнение гиперболы искомый вывод будет доказан.

Пример

Этот метод можно применить к задаче №6 на IMO 1988 : пусть a и b — положительные целые числа, такие, что ab + 1 делит a. ² + б ² . Докажите, что ⁠ a ² + б ² / ab + 1 ⁠ — полный квадрат.

1. Позволять ⁠ a ² + б ² / ab + 1 ⁠ = q и зафиксируйте значение q . Если q = 1 , q является желаемым квадратом. Если q = 2 , то ( a - b ) ² = 2 и не существует интегрального решения a , b . Когда q > 2 , уравнение x ² + и ² − qxy − q = 0 определяет гиперболу H и ( a , b ) представляет целую точку решетки на H .
2. Если ( x , x ) целая точка решетки на H с x > 0 , то (поскольку q целое) можно видеть, что x = 1 . Тогда утверждение этого предложения верно для точки ( x , x ) .
3. Теперь пусть P = ( x , y ) — точка решетки на ветви H с x , y > 0 и x ≠ y (поскольку предыдущее замечание охватывает случай x = y ). По симметрии мы можем предположить, что x < y и что P находится в более высокой ветви H . Применяя формулы Виеты, ( x , qx − y ) является точкой решетки на нижней ветви H . Пусть y ′ = qx − y . Из уравнения для H видно, что 1 + x y ′ > 0 . Поскольку x > 0 , отсюда следует, что ≥ y 0 . Следовательно, точка ( x , y ′ ) находится в первом квадранте. По размышлению точка ( y ′ , x ) также является точкой в ​​первом квадранте H . Более того, из формул Виеты yy ′ = x ² - q и y ′ знак равно ⁠ x ² - д / у ⁠ . Объединив это уравнение с x < y , можно показать, что y ′ < x . Новая построенная точка Q = ( y ′ , x ) тогда находится в первом квадранте, на более высокой ветви H , и с меньшими координатами x , y , чем точка P, с которой мы начали.
4. Процесс предыдущего шага можно повторить всякий раз, когда точка Q имеет положительную координату x . Однако, поскольку координаты x этих точек будут образовывать убывающую последовательность неотрицательных целых чисел, процесс можно повторить только конечное число раз, прежде чем он создаст точку Q = (0, y ) на верхней ветви H ; подстановкой q = y ² является квадратом, как и требуется.

См. также

• Формула Плейса
• Доказательство от противного
• Бесконечный спуск
• Марковское число
• Аполлоническая прокладка

Внешние ссылки

• Vieta Root Jumping на Brilliant.org
• Миллс, штат Вашингтон (1953). «Система квадратных диофантовых уравнений» . Пасифик Дж. Математика . 3 (1): 209–220.