Диофантовы уравнения по простому модулю

2

Диофантовы уравнения по простому модулю

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

Может быть, этом предмет показется мне затруднительным, поскольку мы еще с ним незнаком, а начинающие не склонны надяться на успех. Но он сначала удается твоему усердию и моим погрешиям, либо страстная любовь к науке помогаем быстрювати учение».

Таким посвящением открывается «Арифметика» Диофанта Александриского.

В этой книге Диофант (он жил предположительно в III в.) суммировал и расширил накопленный до него опыт решения неопределенных (т. е. с несколько переменными) алгебраических уравнений в целых или рациональных числах. С тех пор эти уравнения стали называться диофантовыми.

Вот примеры таких уравнений:
$$x^2 + y^2 = z^2, \quad x^2 = y^3 + 5y + 7.$$

Интерес к диофантовым уравнением связан, видимо, с самой природой человека — сохранившие документы обнаруживают его следы в глубине тысячелей. Еще в Древнем Вавилоне занимались поисками пифагоровых проект — целочисленных решений $x^2 + y^2 = z^2$.

«Арифметика» Диофанта легла в основу теории чисел нового времени. Со времен Ферма (XVII в.) диофантовы уравнения стали предметом глубоких исследований самых выдающихся математиков и неослабного интереса всех любителей чисел, не уступающих в revenни достопочтеннойшем Дионисию.

Росло и растет могущество задач, о котором говорится в посвящении. Теория диофантовых уравнений проиталась связями edва ли не со всеми областями современной математики.

Только в одном Диофант ошибся — предмет не стал удобопонятным.

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

Длительный период исследований завершился в 1969 году отрицательным решением этой проблемы: оказалось, что общего способа, о котором говорится в ее формулировке, вообще не существует *).

В связи с диофантовыми уравнением ставились и более простые задачи. При их решения возникали очень красивые теории. О началях одной из них — теории диофантовых уравнений по простому модулю — мы рассекjem в этой стране. Чтобы этот рассказ был вам понятен, советуем перечитать статьи «Сравнения и классы вычетов» (№ 10) и «Сравнения по простому модулю» (№ 11).

Переход к уравнении по простому модулю

Рассмотрим какое-нибудь диофантово уравнение. Предположим, что оно имеет решение, и рассмотрим вместе

*) Подробнее об этом см. «Квант», 1970, № 7.

3

входащих в решение чисел их классы вычетов по mod p. Легко видеть, что полученный набор будет являться решением приведенного уравнения — уравнения, получающейся из данного заменой каждой коэффициента на его класс вычетов по mod p. Поэтому необходимо счеловаться решением у диофанта уравнения является существование решения приведенного уравнения по mod p при всех p*).

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

Каковы целочисленные решения уравнения

$$35x^4 + 24y^3 = 100\ 000?$$

(1)

Приведем это уравнение по mod 3. 35 ≡ 2 (mod 3), 24 ≡ 0 (mod 3), 100\ 000 ≡ 1 (mod 3); поэтому по mod 3 уравнение (1) принимает вид

$$\bar{2}x^4 = \bar{1}.$$

(2)

$$\bar{2}x^4$$ при x ∈ F_3 принимает значения 0 и 2 (проверьте), поэтому у уравнения (2) нет решений, значит, нет решений и у уравнения (1).

Рассмотрим пример последнее:

$$5x^3 + 11y^3 + 13z^3 = 0.$$

(3)

У этого уравнения есть одно очевидное решение: x = y = z = 0. Постаемся доказать, что других решений у него нет.

Естестенно рассмотреть уравнение (3) по modulo 5, 11 или 13 — тогда один из трех членов обратится в 0. Какой же именно modulo нам выбрать?

*) О вычислениях «по modulo» говорится также в статье М. И. Башмакова («Квант», 1971, № 3).

Ответить на этот вопрос нам по-может решение задачи 4 статьи «Сравнения по простому modulo». Из него следует, что в множества F_5 и F_{11} все элементы являются кубами, а в множестве F_{13} только 5 элементов являются кубами.

После приведения уравнения (3) по modulo 5 оно принимает вид

$$y^3 + \bar{3}z^3 = \bar{0}.$$

(4)

Поскольку любой элемент множества F_5 является кубом и в F_5 возможно деление, для любых a и b найдут такие y и z, что y^3 = a и 3z^3 = b. Поэтому в множестве F_5 у уравнения (4) существует много неулевых решений (соответствующих парам a, b, для которых a + b = 0). Аналогичный результат верен и для F_{11}. Поэтому у нас нет найдены, рассматривая уравнение (3) по modulo 5 или 11, доказать, что оно имеет только нулевое решение.

Рассмотрим уравнение (3) по mod 13:

$$\bar{5}x^3 + \bar{11}y^3 = \bar{0}.$$

(5)

В множестве F_{13} кубами является только элементы 0, 1, 5, 8, 12. Составим таблицу возможных значений выражения $\bar{5}a + \bar{11}b$, где a, b ∈ {0, 1, 5, 8, 12} (в пересечении стоит сумма $\bar{5}a + \bar{11}b$). Из таблицы видно, что единственный решением уравнения (5) является x = y = 0.

Значит, для любого решения x_0, y_0, z_0 уравнения (3) x_0 и y_0 делятся на 13: x_0 = 13x_1, y_0 = 13y_1. Подставив эти выражения для x_0 и y_0 в (3),

4

мы получим $5 \cdot 13^3 x_1^3 + 11 \cdot 13^3 y_1^3 + 13 z_0^3 = 0$, откуда $z_0$ делится на 13: $z_0 = 13 z_1$. Подставив и сокращив на 13: $5 x_1^3 + 11 y_1^3 + 13 z_1^3 = 0$. Отсюда следует, что $x_1 = 13 x_2$, $y_1 = 13 y_2$, $z_1 = 13 z_2$, и т. д. Таким образом, $x_0, y_0, z_0$ делятся на любую степень 13, что возможно, только если $x_0 = y_0 = z_0 = 0$.

Teоремы Шевалле и Варнина

Знание множества $F_{13}$ позволяет нам сообщать, какой именно модель сравнения стоит выбрать для исследования уравнения (3).

А что будет, если в уравнении не три переменные, а четыре или пять? Что будет, если степень уравнения — не 3, а 4, 5 или 6? Чувствуется, что если число переменных x уведомляется, то нашши шансы доказать невозможность решения исходного уравнения, рассматривая его по какому-нибудь модели, подают; если же уведомляется его степень — растут. Это интуитивное сообщение можно уточнить.

Справедлива следующая замечательная Теорема Шевалле: рассмотрим множество $R(x_1, x_2, \dots, x_n)$ с коэффициентами в множестве $F_p$; пусть $x_1 = x_2 = \dots = x_n = 0$ — решение уравнения $R(x_1, x_2, \dots, x_n) = 0$; если степень множество $R(x_1, x_2, \dots, x_n)$ меньше n, то уравнения $R(x_1, x_2, \dots, x_n) = 0$ есть и ненулевое решение.

Teорема Шевалле сразу следует из такой теоремы Варнина: если степень множелена $R(x_1, x_2, \dots, x_n) = 0$ равно 0 или $\ge p$. Но первый случай исключен, так как уравнения есть нулевое решение. Значит, у него есть еще по крайней мере p — 1 решение.

Доказательство теоремы Варнина настоящего простого и красivo, что приведем его здесь, но сначала поговорим.

О некоторых суммах, равных нулю

Чему равна сумма $\bar{b}_1 + \bar{b}_2 + \dots + \bar{b}_p$ всех элементов множества $F_p$? Умножим все слагаемые на какой-нибудь элемент $\bar{a}$ из $F_p$, не равный 0 и 1. Тогда сумма умножится на этот же элемент: $\bar{a} \bar{b}_1 + \bar{a} \bar{b}_2 + \dots + \bar{a} \bar{b}_p = \bar{a} (\bar{b}_1 + \bar{b}_2 + \dots + \bar{b}_p)$. С другой стороны, при умножении всех элементов множества $F_p$ на какой-нибудь элемент ($\neq 0$), мы снова получим все элементы из $F_p$; поэтому $\bar{b}_1 + \bar{b}_2 + \dots + \bar{b}_p = \bar{a} (\bar{b}_1 + \bar{b}_2 + \dots + \bar{b}_p)$. Значит, $\bar{b}_1 + \bar{b}_2 + \dots + \bar{b}_p = 0$.

А чем равна сумма $\bar{b}_1^2 + \bar{b}_2^2 + \dots + \bar{b}_p^2$ квадратов элементов множества $F_p$? Умножим снова все элементы на какой-нибудь элемент $\bar{a} (\neq 0, 1)$. Тогда сумма по тем же причине, что и раньше, остается прежней: $(\bar{a} \bar{b}_1)^2 + (\bar{a} \bar{b}_2)^2 + \dots + (\bar{a} \bar{b}_p)^2 = \bar{b}_1^2 + \bar{b}_2^2 + \dots + \bar{b}_p^2$; с другой стороны $(\bar{a} \bar{b}_1)^2 + (\bar{a} \bar{b}_2)^2 + \dots + (\bar{a} \bar{b}_p)^2 = \bar{a}^2 (b_1^2 + \dots + \bar{b}_p^2)$. Если $\bar{a}^2 \neq 0, 1$, то $b_1^2 + \bar{b}_2^2 + \dots + \bar{b}_p^2 = 0$.

И вообщее: если в множестве $F_p$ найдется такой элемент $\bar{a}$, что $\bar{a}^k \neq 0, 1$, то сумма $k$-х степеней всех элементов из $F_p$ равна 0.

Ясно, что если $\bar{a}^k = 1$ для первого многочлена $\bar{a}$ из $F_p$, то тем более $\bar{b}_k = 1$ для всех остальных элементов $\bar{b} \neq 0$. Если $\bar{a}^k = 1$ в том и только в том случае, когда k делится на p — 1. В частности, если $0 < k < p - 1$, то $\bar{a}^k \neq 1$ и сумма k-х степеней равна 0. Поскольку $\bar{0}^{p-1} + \bar{1}^{p-1} + \dots + \bar{p-1}^{p-1} = \bar{p-1}$, а $x^p = x$ для $x \in F_p$ (Малая теорема Ферма), мы нашли сумму k-х степеней элементов из $F_p$ для любого k ≠ 0:

$$\bar{b}_1^k + \bar{b}_2^k + \dots \bar{b}_p^k =$$

$$= \begin{cases} 0, \text{ если } k \neq 0 (\text{mod } p - 1), \\ p - 1, \text{ если } k \equiv 0 (\text{mod } p - 1) \text{ и } k \neq 0. \end{cases}$$

5

Рассмотрим теперь некоторый одночлен $q = x_1^{k_1} x_2^{k_2} \dots x_t^{k_t}$ и всевозможные упорядоченные наборы $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle$, где $\bar{c}_i \in F_p$ ($i = 1, 2, \dots, n$). Таких наборов $p^n$. Будем считать, что $t \leq n$. тогда для каждой набора можно вычислить значение одночлена $q$, принимаем на этом наборе: нужно подставить вместо $x_1, x_2, \dots, x_t$ первый $t$ чисел набора. Чему равна сумма всех этих $p^n$ значений? (Решенная нами задача о сумме $k$-х степеней является частным случайем этой задачи: $q = x_1^k, n = 1$.) Мы предоставляем читателю исследовать этот вопрос.

Для дальнейшего нам понадобится только, что если $t < n$ или $0 < k_i < p - 1$ для некоторого $i$, то исключая сумма равна $0$. Это вы без труда доказательства сами.

Доказательство теоремы Варинга

Обозначим степень многочлена $R(x_1, x_2, \dots, x_n)$ через $m$, число решений уравнения $R(x_1, x_2, \dots, x_n) = 0$ через $N(R)$. Нам надо из условия $m < n$ вывести, что $N(R)$ делится на $p$.

В множество $M$ всевозможных упорядоченных наборов элементов из $F_p$ длины $n$ рассмотрим подмножество $M_R$ решений уравнения $R(x_1, x_2, \dots, x_n) = 0$. Подмножество $M_R$ состоит из наборов $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle$, для которых $R(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n) = 0$.

Рассмотрим функцию $f_R$, которая каждому элементу $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle \in M$ сопоставляет число 1, если $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle \in M_R$, и число 0, если $c \langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle \notin M_R$.

(Функция, определяная на некотором многочстве $M$ и принимающая значение 1 на некотором подмножестве $A \subset M$ и значение 0 на остальных элементов из $M$, называется характеристической функцией подмножества $A$. Таким образом, функция $f_R$ является характеристической функцией подмножества $M_R$.) Из самого определения функции $f_R$ следует, что число решений $N(R)$ уравнения $R(x_1, x_2, \dots, x_n) = 0$ равно сумму значений функции $f_R$ по всем элементам множества $M$. Это утверждение, казалось бы, ничего не добавляет к определению $f_R$. Тем не менее читатель увидит, что замена множества $M_R$ функцией $f_R$ является ключевой в доказательстве.

Рассмотрим теперь функцию $f_R$, которая отличается от функции $f_R$ тем, что вместо чисел 1 и 0 принимает на решении и нерешения соответствующего значения $\bar{1}$ и $\bar{0}$ из $F_p$. Сумма $S(\bar{f}_R)$ значений функции $f_R$ по всем наборам $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle$ равна классу вычетов $N(R)$ (по mod $p$) числа $N(R)$. Поэтому для доказательства теоремы Варинга достаточно убедиться, что $S(\bar{f}_R) = \bar{0}$.

Воспользовавшись Малой теореме Ферма, представим функцию $f_R$ многочленом. Для этого рассмотрим многочлен $Q(x_1, x_2, \dots, x_n) = \bar{1} - R(x_1, x_2, \dots, x_n)^{p-1}$. Если $R(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n) \neq 0$, то Малой теореме Ферма $R(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n) = \bar{0}$. Если $R(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n) = \bar{0}$, то $R(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n)^{p-1} = \bar{0}$ и $Q(\bar{c}_1, \bar{c}_2, \dots, \bar{c}_n) = \bar{1}$. Поэтому $f_R = Q$.

Многочлен $Q(x_1, x_2, \dots, x_n)$ является суммой одночленов: $Q = q_1 + q_2 + \dots + q_l$.

Нам достаточно проверить, что суммы значений каждого из одночленов $q_1, q_2, \dots, q_l$ по всем наборам $\langle \bar{c}_1, \bar{c}_2, \dots, \bar{c}_n \rangle$ равны $\bar{0}$. Тогда и сумма $S(f_R) = S(Q)$ будет равна $\bar{0}$, поскольку $S(Q) = S(q_1) + S(q_2) + \dots + S(q_l)$.

Возьем, например, одночлен $q_1 = x_1^{k_1} x_2^{k_2} \dots x_t^{k_t}$. Степень многочлена $Q$ равна $(p - 1) m$. Поэтому степень одночлена $q_1$ меньше $(p - 1) n$ (по условию теоремы $m < n$). Значит, $k_1 + k_2 + \dots + k_t < (p - 1) n$. Из этого неравенства следует, что либо $t < n$, либо среди $k_1, k_2, \dots, k_t$ найдется показатель $k_i$, для которого $0 < k_i < p - 1$. Равенство $S(q_1) = \bar{0}$ следует теперь из результата, сформированного в конце предыдущого раздела.

Teорема Вейля — Лэнга

Выше мы уже говорили, что если у dioфантов уравнения есть решение

6

нице, то у любого приведенного уравнения (по любому простому modulo $p$) тоже есть решение.

Утверждение: «Если у диофантова уравнения есть ненулевое решение, то у любого приведенного уравнения есть ненулевое решение», не верно. Например, уравнение
$$x^2 + y^2 = 9 = 0$$
имеет ненулевое решение ($x = 3, y = 0$), но по modulo 3 приведенное уравнение
$$x^2 + y^2 = 0$$
таких решений не имеет.

Тем не менее ясно, что если у диофантова уравнения есть ненулевое решение, то для всех $p$, начиная с некоторого, у приведенного уравнения тоже есть ненулевое решение.

Обратное неверно: уравнение
$$x^2 + y^2 + z^2 = 0$$
(6)
по теореме Шевалле имеет ненулевое решение в лию бом $F_p$, а уравнение
$$x^2 + y^2 + z^2 = 0$$
ненулевых решений (не только в $Z$, но и в $R$) не имеет *).

Рассмотрим теперь снова диофантово уравнение
$$R(x_1, x_2, \dots, x_n) = 0$$,
козффициенты которого — целые числа. Интересно знать, каково множество тех простых $p$, для которых существует решение по mod $p$. Ответ на этот вопрос дает замечательная теорема Вейля — Лэнга. Если множество $R(x_1, x_2, \dots, x_n)$ абсолитно приведение, то уравнение $R(x_1, x_2, \dots, x_n) = 0$ имеет решение по простому modulo $p$ для всех $p$, начиная с некоторого.

Под абсолитно приведение многочленом мы будем понимать такой многочлен, который нельзя разложить в произведение двух многочленов по modulo $p$ для всех $p$, начиная с некоторого.

*) Это не очень интересный пример: читатель может проверить, что по modulo 8 уравнение (6) ненулевых решений не имеет. В упомянутой статье М. И. Башмакова указан пример диофантова уравнения ($3x^3 + 4y^3 + 5z^3 = 0$), не имеющего ненулевых решений, для которого приведение уравнение ненулевое решение по лию бому modulo $p$ не имеет.

Условие абсолитной неприводимости в формулировке теоремы существенно: из заданий 2 к статье «Сравнение по простому modulo» следует, что уравнение $x_1^2 + x_2^2 = 0$ разрешимо при $p = 4k + 1$ и неразрешимо при $p = 4k + 3$. Простых чисел вида $p = 4k + 3$ бесконечного много, поэтому заключение теоремы для многочлена $x_1^2 + x_2^2$ не верно. Разумеется, для него неверна и посылака: из разрешимости уравнения $x_1^2 + x_2^2 = 0$ по modulo $p = 4k + 1$ (а простых чисел этого вида тоже бесконечного много) следует, что оно разложимо на множители по этому modulo.

Можно доказать, что «подавляющее большинство» многочленов абсолитно неприводимы.

В отличие от теоремы Варинга, доказательство теоремы Вейля — Лэнга в общем случае очень трудно.

Рассмотрим один очень частный случай уравнения $R(x_1, x_2, \dots, x_n) = 0$: когда многочлен $R$ — первой степени: $R(x_1, x_2, \dots, x_n) = a_1x_1 + a_2x_2 + \dots + a_nx_n + b$ (хотя один из коэффициентов $a_i$ предполагается отличным от 0). Легко видеть, что в этом случае $N(R) = p^{n-1}$. Действительно, можно считать (переставив, если нужно, неизвестен ie), что $a_1 \neq 0$; тогда, придавая $x_2, \dots, x_n$ всевозможные значения из $F_p$ и положив $x_1 = -a_1^{-1}(a_2x_2 + \dots + a_nx_n + b)$, мы получим решение.

Teорему Вейля — Лэнга можно уточнить: при больших $p$
$$|N(R) - p^{n-1}| < c \cdot p^{\frac{n-1}{2}},$$
где $c$ — коэффициент число, зависит от многочлена $R$.

Первоначальное доказательство Вейля основано на открытых им глубоких связях между, казалось бы, дальнейми вопросами: дискретной, и даже конечной, задачей о числе решения уравнения $R(x_1, x_2, \dots, x_n) = 0$ по простому modulo и геометрическим строением непрерывного многочлена комплисных решений этого уравнения, то есть тех наборов комплисных чисел $\langle d_1, d_2, \dots, d_n \rangle$, для которых $R(d_1, d_2, \dots, d_n) = 0$.

Недавно элементарное (не использованное никаких косвенных методов), но тем не менее весба сложное доказательство теоремы Вейля — Лэнга для сверлдовский математик С. А. Степанов.