Математика · объяснение и практика

Как целые решения x²−Dy²=1 продолжают друг друга

Как умножение выражений x+y√D строит новые целые решения уравнения Пелля, проверить сохранение правой части и не объявить произвольный старт полным списком.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

В маршруте Новые структуры целой арифметики · 10 тем

Главная мысль

Если x²−Dy²=1, произведения выражений x+y√D снова дают решения. Для положительного целого неквадратного D степенная конструкция создаёт бесконечные семейства из подходящего ненулевого по y старта.

Целая задача возле иррациональной прямой

Уравнение Пелля имеет вид x²−Dy²=1, где D — положительное целое, не являющееся квадратом, а x и y целые. Всегда есть тривиальные решения с y=0. Интерес представляют положительные x и y: они дают рациональные отношения x/y, близкие к √D, но не равные ему.

Разложение (x+y√D)(x−y√D)=1 показывает полезную структуру. Если перемножить два выражения с такими сопряжёнными произведениями, результат тоже имеет сопряжённое произведение один. Коэффициенты при единице и √D остаются целыми, поскольку D целое. Поэтому умножение не только сохраняет равенство, но и не выводит нас из нужной области чисел.

Проверяемое правило продолжения

Пусть (a,b) — фиксированное положительное решение, а (x,y) — уже найденное. После умножения получаем X=ax+Dby, Y=bx+ay. Тождество X²−DY²=(a²−Db²)(x²−Dy²)=1 подтверждает новый ответ. При положительных a,b,x,y обе координаты растут, так что повторение не зацикливается на старой паре.

Для D=2 подходит (3,2), поскольку 9−8=1. Умножение этого выражения на себя даёт (17,12), а затем на исходный множитель — (99,70). Проверка 17²−2·12²=1 показывает, что увеличение координат не является численным приближением. Здесь всё вычисление точное и целочисленное. Из исходного равенства также видно, что отношение x/y лежит выше корня. Разность равна единице, делённой на y²(x/y+√D), поэтому увеличение положительного знаменателя связано с точностью приближения, а не с округлением самого уравнения.

Пример

При D=3 известен старт (2,1). Какое решение даёт его квадрат?

Получаем X=2²+3·1²=7, Y=2·2·1=4. Проверка: 7²−3·4²=49−48=1. Это следующая пара степенного семейства.

Семейство не всегда доказанный полный список

Если взять не наименьшее положительное решение как старт, его степени могут пропустить решения. Например, при D=2 старт (17,12) порождает лишь часть семейства, получаемого из (3,2). Для утверждения обо всех положительных решениях нужна теорема с минимальным положительным стартом и обоснование полноты, а не только сохранение уравнения.

Случай квадратного D устроен иначе: выражение распадается на целые множители x−dy и x+dy с произведением один. Положительного решения с y>0 тогда нет. Также смена правой части на минус один создаёт другое уравнение: квадрат отрицательного по сопряжённому произведению выражения даёт плюс один, но нечётные степени сохраняют минус один.

От чтения к действию

А теперь — вы

Для D=5 известна пара (9,4). Какое решение даёт квадрат выражения 9+4√5?

Частые вопросы

Нужно ли округлять √D в степенном вычислении?

Нет. Можно вести пары целых коэффициентов по формулам X=ax+Dby, Y=bx+ay и проверять точное исходное равенство.

Все ли степени произвольного положительного решения дают все решения?

Нет. Сохранение уравнения доказывает только семейство. Полная классификация положительных решений использует наименьшее положительное решение.

Углублённый разбор

Уравнение Пелля и период цепной дроби

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

Перед началом: Цепная дробь и подходящая дробь; Целые квадратные числа.

Маленькая норма заставляет дробь хорошо приближать корень

Пусть D — положительное неквадратное целое, x,y>0 и x²−Dy²=±1. Тогда x и y взаимно просты, а |x/y−√D|=1/(y²(x/y+√D)). Это особенно сильное рациональное приближение. Теорема о подходящих дробях утверждает, что такие положительные решения находятся среди подходящих дробей √D. Поэтому бесконечный перебор пар заменяется структурированной последовательностью рациональных кандидатов.

Знаменатель y здесь не нулевой: тривиальное решение (1,0) не помогает приближать корень и исключается из поиска положительного старта. После получения кандидата всегда вычисляйте точную норму x²−Dy². Близость десятичного отношения к √D не различает норму +1, −1 или другое малое целое и сама по себе не удостоверяет уравнение.

Период различает два знака уравнения

У √D простая цепная дробь имеет вид [a₀; overline(a₁,…,aℓ)] с конечным периодом длины ℓ. Для уравнения с правой частью +1 первый положительный старт получается в конце первого периода, если ℓ чётно, и второго, если ℓ нечётно. Для правой части −1 решение существует ровно при нечётном ℓ. Это точная теорема о квадратичных иррациональностях, а не эмпирическое правило нескольких первых десятичных знаков.

При вычислении периода удобнее хранить точное выражение с √D и рациональным знаменателем. Округлённая арифметика может ошибиться в целой части возле границы и получить ложное повторение. Подходящие дроби восстанавливаются рекуррентно: pⱼ=aⱼpⱼ₋₁+pⱼ₋₂, qⱼ=aⱼqⱼ₋₁+qⱼ₋₂, со стартами p₋₂=0,p₋₁=1,q₋₂=1,q₋₁=0.

Минимальность удобно подтвердить коротким отдельным аргументом

Для маленького D найденный первый знаменатель можно независимо сравнить с меньшими y, проверяя, является ли Dy²+1 квадратом. Это не доказывает общую теорему о периодах, зато проверяет конкретный минимальный старт другим методом. Отсутствие решения −1 иногда дополнительно видно по одному простому модулю. Модульный запрет является самостоятельным отрицательным свидетельством и полезно согласуется с чётностью периода.

Первый старт для D=11

Условие. Найдите период цепной дроби √11, минимальное положительное решение x²−11y²=1 и решите вопрос о правой части −1.

  1. Целая часть √11 равна 3. Обращение остатка даёт 1/(√11−3)=(√11+3)/2, чья целая часть тоже 3.
  2. Его остаток равен (√11−3)/2, обратный к нему равен √11+3 с целой частью 6. После вычитания 6 возвращается √11−3. Поэтому запись равна [3; overline(3,6)], период имеет длину 2.
  3. Первые подходящие дроби равны 3/1 и 10/3. Их нормы равны −2 и 100−99=1. Для y=1,2 значения 11y²+1 равны 12,45 и не являются квадратами. Значит минимальный положительный старт — (10,3).
  4. Чётный период запрещает уравнение с −1. Независимо оно потребовало бы x²≡−1 (mod11), но квадраты modulo11 равны 0,1,3,4,5,9 и не содержат 10.

Ответ. √11=[3; overline(3,6)]; минимальное решение +1 равно (10,3), решений −1 нет.

Проверка. Целые квадраты проверяют минимальность без повторения цепной дроби, а полный набор квадратных остатков modulo11 независимо подтверждает невозможность отрицательной нормы.

Где легко ошибиться. Не переносите правило продолжения на поиск наименьшего старта. Случайно найденное большое решение может пропускать меньшие, а малая десятичная ошибка отношения не удостоверяет норму ±1.

Проверьте понимание

Каково минимальное положительное решение x²−11y²=1?

Вопросы к этой главе

Почему период длины 2 заканчивается дробью 10/3, а не следующим членом 6?

Индексация начинается с a₀ вне периодической части. Для чётного ℓ старт +1 находится на индексе ℓ−1, здесь 1. Подстановка точной нормы предотвращает типичное смещение на один член.

Чётность периода нужна для квадратного D?

Нет: у целого √D цепная дробь конечная и эта теорема о квадратичной иррациональности не применяется. Само уравнение тогда распадается на два целых множителя, и положительного решения с y>0 нет.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Keith Conrad: Pell’s Equation II, §5

    Прочитаны Theorem5.1 и Corollary5.2: решения ±1 входят в подходящие дроби √D, связь с периодичностью. Наш период √11 получен прямым обращением, минимальность проверена целыми квадратами, невозможность −1 отдельно проверена modulo11; степенное продолжение SQL-главы не повторяется.

Уравнение x²−Dy²=N: несколько орбит вместо одной цепочки

Для ненулевой нормы N умножение на единицу нормы один сохраняет уравнение x²−Dy²=N, но одна стартовая точка может не породить все решения. Полуинтервал по величине x+y√D позволяет выбрать конечный список представителей. Он одновременно доказывает полноту найденных орбит и различает их.

Перед началом: Норма x+y√D и её мультипликативность; Положительная единица решения Пелля.

Действие единицы сохраняет целочисленность и норму

Зафиксируем D=2, N=7 и ε=3+2√2 с нормой один. Умножение α=x+y√2 на ε даёт x′=3x+4y, y′=2x+3y. Обратное умножение на 3−2√2 тоже имеет целые коэффициенты. Поэтому все целые степени ε действуют на решениях, не меняя норму семь.

Орбитой назовём множество αεᵏ при целых k. Положительность α сохраняется. Для решений с x>0 и y≥0 имеем α≥√7 и сопряжённое число x−y√2=7/α>0. Из α можно восстановить x=(α+7/α)/2 и y=(α−7/α)/(2√2).

Полуинтервал выбирает единственного представителя орбиты

Для любого α>0 существует единственное целое k, переводящее его умножением на εᵏ в [√7, ε√7). Это обычное масштабирование положительного числа фиксированным множителем больше единицы. Полуоткрытая граница устраняет двойное представление соседними степенями.

В этом интервале y≥0 и y<[(ε−ε⁻¹)√7]/(2√2)=2√7. Значит, целые представители ищутся лишь при y=0,1,…,5. Это конечный поиск, выведенный из нормы и масштаба, а не произвольное ограничение перебора. Различные представители внутри одного такого полуинтервала не могут быть связаны ненулевой степенью ε.

Полнота относится к указанным знакам и выбранному действию

Проверка конечного списка даёт все орбиты положительных решений относительно ε. Для x>0,y≥0 их дальнейшие положительные члены получаются неотрицательными степенями от выбранных представителей. Отрицательные координаты добавляются отдельно сопряжением и общим знаком, если задача требует все целые решения.

Нельзя объявить одну обнаруженную последовательность полным списком только потому, что её члены растут и сохраняют норму. Нужна редукция произвольного решения к проверенному начальному диапазону. Именно здесь ненулевая норма отличается от привычной цепочки решений нормы один: в диапазоне может оказаться несколько стартов.

Две орбиты нормы семь

Условие. Найдите все представители решений x²−2y²=7 с x>0,y≥0 в диапазоне √7≤x+y√2<ε√7. Покажите первые два члена каждой положительной орбиты.

  1. Из редукционной границы y<2√7 следует 0≤y≤5. Значения x²=7+2y² равны 7,9,15,25,39,57.
  2. Квадратами среди них являются только 9 и 25. Получаем представителей (3,1) и (5,3); оба дают норму семь.
  3. Их положительные α равны 3+√2 и 5+3√2. Оба лежат в выбранном полуинтервале, поэтому никакая ненулевая степень ε не переводит один в другой.
  4. Умножение первого представителя на ε даёт (13,9), второго — (27,19). Нормы проверяются: 169−162=7 и 729−722=7.
  5. Обратные формулы возвращают (13,9) к (3,1), а (27,19) к (5,3). Любое другое положительное решение редуцируется к одному из двух представителей по доказанной границе.

Ответ. Имеются две орбиты: от (3,1) и от (5,3). Первые продолжения равны соответственно (13,9) и (27,19).

Проверка. Конечный перебор выведенного диапазона y≤5 доказывает полноту стартов. Прямые и обратные целочисленные рекурсии независимо проверяют их продолжение и различие.

Где легко ошибиться. Не переносите полноту одной орбиты нормы один на произвольную правую часть N. Сохранение нормы при умножении даёт семейство, но не доказывает, что других начальных орбит нет.

Проверьте понимание

Сколько представителей положительных орбит находится в указанном полуинтервале?

Вопросы к этой главе

Почему нужен полуоткрытый интервал?

Если включить обе масштабно связанные границы, одна орбита могла бы получить два представителя. Интервал с включённой нижней и исключённой верхней границей задаёт единственный масштабный представитель.

Нужно ли перебирать y дальше пяти для поиска стартов?

Нет. Ограничение y<2√7 выведено для каждого редуцированного представителя. Более крупное решение сначала переводится в этот диапазон обратными степенями ε и не создаёт новую орбиту.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • K. Conrad: Pell’s equation, II, §3

    Прочитан §3 о редукции решений ненулевой нормы к конечному диапазону посредством единицы. Здесь выбран собственный полуинтервал без симметризации, отдельно выведена его граница и рассчитан пример D=2,N=7; примеры источника не воспроизводятся.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться