Введение

В области теории чисел уравнение Пелля (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\), и соприкоснуться с глубокими свойствами чисел.