Введение

В области теории чисел уравнение Пелля (Pell’s equation) известно как одно из самых красивых диофантовых уравнений, имеющих глубокую теоретическую подоплеку. В этой статье мы предоставим очень подробное объяснение, начиная с базового определения и свойств этого уравнения, до элегантного и эффективного метода решения с использованием цепных дробей (Continued fractions) и механизма генерации бесконечного множества его решений. Для всех, кто любит математику, мы охватили все: от вывода формул до визуализации алгоритмов и реализации с использованием языка программирования.

1. Что такое уравнение Пелля?

Уравнение Пелля — это квадратное диофантово уравнение с двумя переменными, имеющее следующий вид:

Здесь $n$ — положительное целое число, которое не является квадратом (свободно от квадратов или, по крайней мере, не является точным квадратом). Наша цель — найти пары неизвестных целых чисел $x$ и $y$, удовлетворяющих этому уравнению. Представим на мгновение, что $n$ — это точный квадрат, то есть $n = k^2$ (где $k$ — целое число). Тогда уравнение можно преобразовать следующим образом:

Поскольку $x$, $y$ и $k$ являются целыми числами, $(x - ky)$ и $(x + ky)$ также должны быть целыми числами. Единственные комбинации целых чисел, произведение которых равно 1, это $(1, 1)$ или $(-1, -1)$. Решение этого дает $y = 0$, что означает, что решения ограничиваются очень простыми: $(x, y) = (\pm 1, 0)$. Следовательно, в уравнении Пелля условие, что $n$ не является точным квадратом, выступает важнейшей предпосылкой для нахождения значимых решений.

2. Историческая справка: Пелль, Ферма и древнеиндийские математики

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

Позже Леонард Эйлер ошибочно связал имя английского математика Джона Пелля с этим уравнением, и с тех пор оно стало широко известно как «уравнение Пелля». Сам Пелль не играл центральной роли в методе решения этого уравнения.

Если заглянуть дальше в прошлое, индийские математики Брахмагупта и Бхаскара II вычисляли решения уравнений этого типа, используя сложный алгоритм, называемый методом Чакравала, за сотни лет до Ферма. История исследований математиками от древности через средневековье до наших дней запечатлена в этом уравнении.

3. Разница между тривиальными и нетривиальными решениями

Для уравнения Пелля $x^2 - ny^2 = 1$, независимо от значения $n$, всегда существует решение $(x, y) = (\pm 1, 0)$. Подстановка их в уравнение дает $1^2 - n \cdot 0^2 = 1$, что, очевидно, верно. Это называется тривиальным решением (trivial solution).

Однако то, что действительно интересует математиков, — это нетривиальное решение (non-trivial solution), где $y \neq 0$. Удивительно, но если $n$ — положительное целое число, не являющееся точным квадратом, математически доказано, что уравнение Пелля имеет бесконечное множество нетривиальных решений. Более того, среди этих бесконечных решений наименьшее решение, где и $x$, и $y$ — положительные целые числа, называется фундаментальным решением (fundamental solution), и как только оно найдено, все остальные решения могут быть легко сгенерированы с помощью алгебраических операций.

4. Глубокая связь между цепными дробями и уравнением Пелля

Самым мощным и стандартным инструментом для эффективного нахождения фундаментального решения является цепная дробь (Continued fraction). Поскольку иррациональное число $\sqrt{n}$ не может быть представлено конечной дробью, оно может быть красиво выражено как бесконечная периодическая правильная цепная дробь.

Здесь $a_0$ — целая часть $\sqrt{n}$ (т. е. $\lfloor \sqrt{n} \rfloor$), а часть под чертой представляет собой периодическую часть цепной дроби. Пусть длина этого периода равна $m$.

Рациональное число $\frac{p_i}{q_i}$, полученное усечением цепной дроби на определенном члене, называется подходящей дробью (convergent). Подходящие дроби обеспечивают наилучшие рациональные приближения для иррационального числа $\sqrt{n}$. Удивительно, но фундаментальное решение $(x_1, y_1)$ уравнения Пелля получается непосредственно из числителя $p$ и знаменателя $q$ определенной подходящей дроби в разложении $\sqrt{n}$ в цепную дробь. В частности, оно определяется длиной периода $m$ следующим образом:

• Если период $m$ четный: Фундаментальным решением является $(p_{m-1}, q_{m-1})$.
• Если период $m$ нечетный: Фундаментальным решением является $(p_{2m-1}, q_{2m-1})$.

5. Нахождение фундаментального решения: подробное объяснение алгоритма

Подходящие дроби $\frac{p_i}{q_i}$ можно очень быстро вычислить на компьютере, используя следующие рекуррентные соотношения.

Начальные условия задаются следующим образом, чтобы алгоритм мог плавно стартовать:

• $p_{-1} = 1, \quad p_{-2} = 0$
• $q_{-1} = 0, \quad q_{-2} = 1$

Каждый член $a_i$ цепной дроби также может быть найден последовательно, используя только целочисленные арифметические операции. Это обеспечивает точные целочисленные вычисления, которые полностью исключают ошибки арифметики с плавающей запятой.

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

  flowchart TD
    Start["Начало: Ввод целого числа n"] --> CheckSquare["Определить, является ли n точным квадратом"]
    CheckSquare --|"Да"| Trivial["Существуют только тривиальные решения (Конец)"] --> End["Конец"]
    CheckSquare --|"Нет"| InitContFrac["Инициализировать рекуррентность для цепной дроби"]
    InitContFrac --> CalcNext["Вычислить следующий член a_i и подходящую дробь (p_i, q_i)"]
    CalcNext --> CheckEq["Условие: Оценить p_i^2 - n * q_i^2 == 1"]
    CheckEq --|"Ложь"| CalcNext
    CheckEq --|"Истина"| Found["Найдено фундаментальное решение (x_1, y_1) = (p_i, q_i)"] --> End

6. Конкретный пример: разложение в цепную дробь и фундаментальное решение для n = 7

Вместо абстрактной теории, давайте проследим вычисления для конкретного случая $n = 7$. Уравнение Пелля принимает вид $x^2 - 7y^2 = 1$.

Сначала целая часть $\sqrt{7}$ равна $a_0 = 2$. Повторяя операцию взятия обратного значения оставшейся десятичной части и извлечения целой части, разложение $\sqrt{7}$ в цепную дробь оказывается следующим:

Период равен $m = 4$, что является четным числом. Поэтому фундаментальное решение должно быть получено из подходящей дроби $\frac{p_3}{q_3}$. Давайте по порядку вычислим подходящие дроби, используя рекуррентные соотношения.

• $i=0$: При $a_0=2$, $\frac{p_0}{q_0} = \frac{2}{1}$
• $i=1$: При $a_1=1$, $p_1 = 1 \times 2 + 1 = 3$, $q_1 = 1 \times 1 + 0 = 1$. Таким образом, $\frac{p_1}{q_1} = \frac{3}{1}$
• $i=2$: При $a_2=1$, $p_2 = 1 \times 3 + 2 = 5$, $q_2 = 1 \times 1 + 1 = 2$. Таким образом, $\frac{p_2}{q_2} = \frac{5}{2}$
• $i=3$: При $a_3=1$, $p_3 = 1 \times 5 + 3 = 8$, $q_3 = 1 \times 2 + 1 = 3$. Таким образом, $\frac{p_3}{q_3} = \frac{8}{3}$

Давайте проверим, подставив полученное $(p_3, q_3) = (8, 3)$ в уравнение. $8^2 - 7 \times 3^2 = 64 - 7 \times 9 = 64 - 63 = 1$. Оно идеально удовлетворяет условию, поэтому становится фундаментальным решением $(x_1, y_1) = (8, 3)$ для $n = 7$.

7. Генерация бесконечного числа решений: подход с использованием матриц и рекуррентностей

Как только найдено хотя бы одно фундаментальное решение $(x_1, y_1)$, все остальные положительные целочисленные решения $(x_k, y_k)$ могут быть сгенерированы до бесконечности из следующего алгебраического соотношения.

Раскладывая это выражение и сравнивая рациональную часть и иррациональную часть (коэффициент при $\sqrt{n}$), мы получаем рекуррентное соотношение для вычисления следующего решения $(x_{k+1}, y_{k+1})$ из предыдущего решения $(x_k, y_k)$. Выражение этого в матричном формате дает очень аккуратную форму.

Любое $k$-е решение также можно вычислить напрямую, используя возведение матрицы в степень следующим образом:

Это свойство убедительно свидетельствует о том, что решения уравнения Пелля — это не просто последовательности чисел, а они обладают алгебраической структурой (структурой группы).

8. Тождество Брахмагупты и метод Чакравала

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

Блестящим аспектом этого тождества является то, что, комбинируя решение $(x_1, y_1)$ для $x^2 - ny^2 = k_1$ и решение $(x_2, y_2)$ для $x^2 - ny^2 = k_2$, можно напрямую синтезировать новое решение $(X, Y)$ такое, что $X^2 - nY^2 = k_1 k_2$.

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

9. Пример реализации на Python и объяснение

Теперь, когда мы полностью понимаем теоретическую базу, давайте действительно напишем программу. Следующий скрипт на Python выполняет рекуррентность для цепной дроби для заданного $n$ и ищет фундаментальное решение уравнения Пелля. Поскольку он полностью оперирует целочисленной арифметикой без использования чисел с плавающей запятой, нет опасений по поводу потери точности.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import math

def is_square(n):
    """
    Функция для быстрого определения, является ли заданное число n точным квадратом.
    """
    s = math.isqrt(n)
    return s * s == n

def solve_pell(n):
    """
    Вычисляет фундаментальное решение уравнения Пелля x^2 - n * y^2 = 1 с использованием метода цепных дробей.
    Возвращает: Кортеж фундаментального решения (x, y). Возвращает None для точных квадратов.
    """
    if is_square(n):
        return None  # Нет нетривиальных решений для точных квадратов

    # Инициализация для вычислений цепной дроби
    m = 0
    d = 1
    a0 = math.isqrt(n)
    a = a0
    
    # Начальная настройка для подходящих дробей (p_{-1}=1, p_{-2}=0, q_{-1}=0, q_{-2}=1)
    num1, num2 = 1, 0  # p_{i-1}, p_{i-2}
    den1, den2 = 0, 1  # q_{i-1}, q_{i-2}
    
    # Первая подходящая дробь (p_0, q_0)
    num = a0
    den = 1
    
    # Цикл до тех пор, пока не будет выполнено условие x^2 - n*y^2 == 1
    while num * num - n * den * den != 1:
        # Вычислить следующий член a_i цепной дроби
        m = d * a - m
        d = (n - m * m) // d
        a = (a0 + m) // d
        
        # Обновить подходящие дроби p_i, q_i
        num2 = num1
        num1 = num
        den2 = den1
        den1 = den
        
        num = a * num1 + num2
        den = a * den1 + den2

    return num, den

# Пример использования: При n = 7
n = 7
solution = solve_pell(n)
if solution:
    x, y = solution
    print(f"Фундаментальное решение для n={n}: x={x}, y={y}")
    print(f"Проверка: {x}^2 - {n}*{y}^2 = {x**2 - n * y**2}")

Когда этот код выполняется, фундаментальное решение $(x, y) = (8, 3)$ выводится мгновенно, точно так же, как мы рассчитывали это вручную ранее. Если вы попробуете использовать большее значение $n$, например $61$, вы можете убедиться, что решение превращается в огромные числа ($x = 1766319049, y = 226153980$), позволяя вам по-настоящему почувствовать глубокую сложность уравнения Пелля.

10. Мост к алгебраической теории чисел: Связь с теоремой Дирихле о единицах

Уравнение Пелля — это не просто головоломка с целыми числами. В современной математике оно позиционируется как жизненно важный путь к теории вещественных квадратичных полей $\mathbb{Q}(\sqrt{n})$.

Решения уравнения Пелля тесно связаны с единицами (элементами, обратные к которым также являются алгебраическими целыми числами) в кольце алгебраических целых чисел вещественного квадратичного поля. Фундаментальное решение соответствует фундаментальной единице (fundamental unit), которая генерирует эту группу единиц, и тот факт, что для уравнения Пелля существует бесконечное множество решений, можно рассматривать как частный случай более продвинутой теоремы — теоремы Дирихле о единицах (Dirichlet’s unit theorem). Понимание свойств фундаментальной единицы имеет решающее значение для глубокого исследования формул числа классов квадратичных полей и структуры классов идеалов.

11. Заключение

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

Тот факт, что классические задачи, рассмотренные Ферма и Брахмагуптой сотни лет назад, могут быть красиво реализованы в виде современных компьютерных алгоритмов, и в дальнейшем связаны с передовой алгебраической теорией чисел, вызывает глубокую и вневременную математическую романтику. Мы надеемся, что вы воспользуетесь этой возможностью, чтобы применить код на Python и исследовать мир уравнения Пелля для различных значений $n$, и соприкоснуться с глубокими свойствами чисел.