Простые делители оберквадратов

Мы с вами сейчас проведем небольшое исследование, в котором будет и экспериментальная часть, и объяснение. Единственное, чем будет отличаться наша работа от полноценного научного исследования, — это тем, что авторам результат известен. Тем большая нагрузка ляжет на читателей.

Простые делители оберквадратов

Начнем со знакомства с терминологией. Надеемся, что всем известно слово «унтерофицер» — чин чуть ниже офицера. И есть менее известное слово «оберкондуктор». Этот, наоборот, немножко главнее кондуктора.

Так вот, унтерквадраты — это

0, 3, 8, 15, 24, 35 и т.д,

то есть числа, которые на единицу меньше квадрата. А оберквадраты — это

2, 5, 10, 17, 26 и т.д.,

то есть числа, следующие за квадратами.

Итак, перед нами есть два ряда натуральных чисел. Нас интересуют простые делители этих двух рядов чисел (конечно, кроме 0). Для унтерквадратов можно записать общую формулу n² – 1, и это сразу можно разложить на множители: n² – 1 = (n – 1)(n + 1).
В силу этой формулы, ничего интересного сказать про делители унтерквадратов мы не можем, так как они заведомо разлагаются на два множителя, пробегающие все числа, поэтому любое простое число делит какой-нибудь унтерквадрат. Поэтому мы с унтерквадратами попрощаемся и заниматься будем исключительно простыми делителями оберквадратов. Для них тоже есть общая формула n² + 1, но, как вы понимаете, ее на множители (во всяком случае, обычные «школьные») разложить нельзя. Так что тут есть интрига.

Задача 1.Какие простые числа могут быть делителями оберквадратов n² + 1 (n N)?

Давайте начнем раскладывать оберквадраты. (Договоримся писать множители по возрастанию.) Получим такую таблицу:

2 = 2,
5 = 5,
 10 = 25,
17 = 17,
   26 = 213,
37 = 37,
    50 = 255,
   65 = 513,
   82 = 241.

(Когда число простое, запишем «разложение» в виде такого, вроде бы бессмысленного, равенства: 2 = 2, 5 = 5 и т.д.) Нетрудно сообразить, что через раз среди оберквадратов будут встречаться нечетные числа. Можно заметить, что в этой таблице далеко не все простые числа. Давайте выпишем подряд первые простые числа и выделим из них те, которые являются множителями оберквадратов:

(Проверьте, что 53 — тоже делитель какого-то оберквадрата.)

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

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

Чтобы удобнее было анализировать ситуацию, соберем наши числа в две группы:

2, 5, 13, 17, 29, 37, 41, 53, ... — хорошие,

3, 7, 11, 19, 23, 31, 43, 77, ... — плохие.

Как видно, простые числа, идущие через 2 (они называются близнецами), оказываются в разных группах. Если основная закономерность вам еще не бросилась в глаза, давайте посмотрим на последовательные скачки между хорошими или плохими числами. (Скачком мы называем разность между двумя последовательными числами.) Будем писать их над пробелами между числами. Сначала выпишем скачки для хороших чисел:

Теперь скачки для плохих чисел:

Сразу видно, что все скачки, кроме первого, четные. Это легко понять, потому что существует единственное четное простое число 2, а все остальные нечетные. Однако среди скачков встречаются не все четные числа, а числа 4, 8, 12, ... Какой простой закон выделяет из всех четных чисел именно эти? Все эти числа делятся на 4!

Значит, разности чисел из одной группы делятся на 4. Переформулируем это чуть менее привычным для вас образом. Если разность двух чисел делится на 4, то эти числа имеют одинаковый остаток при делении на 4. Смотрим:

2 = 04 + 2,           5 = 41 + 1,
3 = 04 + 3,           7 = 41 + 3,

13 = 43 + 1,         17 = 44 + 1,           ...,
11 = 42 + 3,         19 = 44 + 3,           ...

Итак, прямые наблюдения привели нас к предположению.

Предположение 1. Хорошие числа — это 2 и числа вида 4n + 1, а плохие — это числа вида 4n + 3, где nN.

Можно проверить эту гипотезу для больших чисел на компьютере, например, в системе Maple.
Скажем, 1 000 001 = 1019901, а 2007² + 1 = 25²13197. Нетрудно видеть, что остатки всех множителей при делении на 4 равны 1, а значит, пока что наша гипотеза подтверждается.

На этом экспериментальная фаза закончена. Чтобы доказать гипотезу, мы перейдем в другую область; это часто бывает полезно в математике.

Какие бывают числовые множества? Наряду с натуральными числами существует огромное количество других множеств, в том числе конечных. Самому старому конечному множеству две тысячи лет от роду. Чтобы его описать, составим таблицы сложения и умножения для четных и нечетных чисел:

Нечетные числа при делении на 2 дают остаток 1. Для единообразия будем, вопреки школьной привычке, говорить, что четные числа при делении на два дают остаток 0.

Перепишем эти таблицы, ставя вместо Ч остаток 0, а вместо Н остаток 1:

Мы описали это множество вслед за древними греками, но назовем его по-современному: это поле вычетов по модулю два. Обозначается оно F₂. (Это общепринятое обозначение, в отличие от «оберквадратов» и «хороших чисел».) Обратите внимание, что F пишется тем же шрифтом, что и N.

Теперь опишем более сложное поле вычетов по модулю 5. Вот его таблица сложения:

Но для нашей гипотезы важнее таблица умножения:

(В каждой строке все числа встречаются по одному разу — постарайтесь это доказать.)

Теперь вернемся к задаче 1 и переформулируем ее на новом языке. Заметим, что утверждение «x² + 1 делится на p» равносильно такому:

x² = –1 в F_p. (1)

(Мы знаем, что в натуральных числах уравнение (1) не имеет решений. Однако в полях вычетов дело обстоит совсем иначе. Например, в F₅ элемент –1 — это то же самое, что 4. А ведь 4 — как раз квадрат!)

Таким образом, задача 1 сводится к следующей задаче.

Задача 2.  Для каких простых p уравнение x² = –1 разрешимо (то есть имеет место решение) в поле F_p?

Исследуем уравнение (1). Начнем с поля F₅, для которого все готово. Рассмотрим остатки от деления на 5 при возведении чисел в степень. (Поскольку в этом поле определено умножение, то определена и степень.) Будем выписывать каждое число вместе с его степенями, пока не дойдем до единицы:

1,
2,4,3,1,
2,4,2,1,
4,2 ^* .

Видим, что число 4, то есть –1, в двух случаях встречается на втором месте, иными словами, является квадратом некоторого элемента из F₅ (собственно, квадратом предыдущего элемента: 4 = 2² = 3²).

Теперь рассмотрим последовательности степеней в полеF₇:

У нас встречается число 6, то есть –1 в поле F₇, однако оно каждый раз стоит либо на третьем, либо на первом месте в строке, и следовательно, не является квадратом!

Построим таблицу для поля F₁₃:

2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1,
3, 9, 1,
4, 3, 12, 9, 10, 1,
5, 12, 8, 1,
6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1,
...

Выделенные числа, равные –1 в поле F₁₃, опять встречаются на четных местах, то есть являются квадратами элементов с вдвое меньшим номером в строке. В самом деле,

a^2k = –1 b² = –1, где b = a^k.

Постройте самостоятельно таблицу для поля F₁₁ и убедитесь, что элемент 10, то есть –1 в поле F₁₁, встречается только на нечетном месте в строке и поэтому не может являться квадратом.

Продолжая строить таблицы для полей F₁₇, F₁₉ и т.д., можно обнаружить следующее: в полях порядка 4n + 1 элемент –1 встречается на четном месте в строке, а в полях порядка 4n + 3 не встречается. То есть поля разбиваются на два типа по тому же правилу, которое мы открыли для хороших и плохих чисел.

Предположение 2. Уравнение (1) разрешимо в поле F_p, если p = 4n + 1 или p = 2, и неразрешимо, если p = 4n + 3.

Если мы сможем доказать это предположение, то автоматически будет доказано и эквивалентное ему предположение 1.

Рассмотрим в общем виде последовательность степеней элемента a в поле F_p. Сейчас нам удобнее начинать ее с 1:

1, a, a², a³, ...

Теперь ответим на несколько вопросов.

1. Почему последовательность зацикливается?

Следующий элемент в последовательности степеней (при заданном a) определяется только предыдущим. Значит, если элемент повторился, то и вся последовательность с этого места повторяется. Однако ненулевых элементов в поле F_p конечное число (а именно, p – 1), поэтому элементы обязательно начнут повторяться.

2. Почему повторение начинается с 1, а не с какого-то из следующих элементов?

Поскольку каждый элемент в строке a таблицы умножения встречается один раз, то он представим в виде произведения элемента a на какой-то элемент единственным образом. Тем самым, последовательность можно продолжать (по одному элементу!) не только вперед, но и назад. Скажем, если повторился элемент a^k, то перед ним обязательно будет a^k – 1, перед тем — a^k – 2, ..., a, 1.

3. Что такое цикл?

Запишем повторяющуюся часть последовательности по кругу:

Она и называется циклом. Теперь нам опять лучше сдвинуть начало цикла и отсчитывать его от a. Все время выписывать цикл по кругу неудобно, поэтому напишем его в строчку, помня, что после 1 опять идет a и т.д.:

{a, a², a³, ..., 1}.

4. Какова длина цикла?

Длина цикла в поле F_p не больше p – 1, так как ненулевых элементов ровно p – 1. Наибольшая длина цикла достигается, когда в нем встречаются все ненулевые элементы поля F_p. (Проверьте по нашим таблицам, что такое бывает.)

Определение. Элемент a, последовательность степеней которого пробегает все элементы поля F_p, называется первообразным корнем для числа p.

Есть теорема, утверждающая, что для любого простого p первообразный корень существует ^** . Это самое глубокое утверждение в нашем исследовании, мы его оставим без доказательства.

Если же a — не первообразный корень, то оказывается, что цикл укладывается в отрезке p – 1 целое число раз. (Проверьте по нашим таблицам.) Тем самым, на месте p – 1 всегда стоит 1. Это малая теорема Ферма.

Осталось заметить, что если на k-м месте стоит –1 или 1, то на месте 2k (с вдвое большим номером) стоит 1. Обратно, если на месте 2k стоит 1, то на k-м месте (с вдвое меньшим номером) — либо 1, либо –1 ((–1)² = 1, 1² = 1).

Теперь мы готовы доказать предположение 2.

Пусть p = 4n + 1. Имеем 4n ненулевых элементов. Выпишем степени первообразного корня для p:

a, a², a³, ..., a⁴ⁿ = 1.

По последнему замечанию, на месте 2n (с вдвое меньшим номером) может оказаться либо 1, либо –1. Однако 1 не может там быть, так как тогда цикл будет содержать лишь половину элементов F_p. Значит, там обязательно окажется –1. То есть квадрат числа, стоящего на месте n, равен –1, и уравнение (1) разрешимо (Случай p = 2 разберите самостоятельно.).

Теперь пусть p = 4n + 3. У нас 4n + 2 элемента. Докажем, что –1 не может попасть на четное число. Все возможные номера элемента 1 в последовательности степеней имеют вид где m — любой из делителей числа 4n + 2. Элемент –1 может стоять только на месте с вдвое меньшим номером, чем 1, то есть на месте Например, если элемент a — первообразный корень для p, то –1 стоит на месте 2n + 1 (на середине). Но это место нечетно. Значит, уравнение (1) неразрешимо.

Тема для дальнейшего исследования.

Какие натуральные числа представимы в виде суммы квадратов двух целых чисел? Для каких n N пара x, y N, для которой n = x² + y и x > y, единственна? Для каких n N существуют две такие пары? Три пары? И т. д.

Терминологическая справка.

Термин «оберквадрат» ввел из педагогических соображений Г.Б. Шабат. Решение задачи об оберквадратах не ново.

Желаем успехов в ваших будущих исследованиях. Если у вас возникнут вопросы, их можно задать по адресу sgibnev@mccme.ru 

---

* Выпишем длины этих строк: 1, 4, 4, 2. Если проделать такие же действия для других простых чисел p вместо 5, то вы обнаружите некоторые интересные закономерности для длин циклов степеней в поле Fp.
** Для составного — не обязательно. Придумайте примеры.

Сгибнев А., Шабат Г.