Сегодня ночью была бессонница. От нечего делать занялся арифметикой.
Гипотеза
Если простое число возвести в квадрат и отнять единицу, то получится
2² – 1 = 3;
5² – 1 = 24;
7² – 1 = 48;
11² – 1 = 120;
13² – 1 = 168;
17² – 1 = 288;
и т.д.
Что объединяет все эти результаты? Они все делятся на 3! [Целое число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3 — средняя школа.]
Но ой! Я пропустил простое число 3. Ну конечно, ведь 3² делится на 3, поэтому 3² – 1 не делится. Других простых чисел, делящихся на 3, нет.
Появилась гипотеза: для любого простого p > 3 число p² – 1 делится на 3. Сенсация! Открытие в мире простых чисел! Такая же безумно сложная задача, как распределение простых чисел, которое всё никак не даётся математикам.
Анализ
А может, просто всё дело в том, что эти простые числа нечётны? Давайте посчитаем:
3² – 1 = 8 — не делится;
5² – 1 = 24 — делится;
7² – 1 = 48 — делится;
9² – 1 = 80 — не делится;
11² – 1 = 120 — делится;
13² – 1 = 168 — делится;
15² – 1 = 224 — не делится;
17² – 1 = 288 — делится;
19² – 1 = 360 — делится;
21² – 1 = 440 — не делится;
23² – 1 = 528 — делится;
25² – 1 = 624 — делится;
27² – 1 = 728 — не делится...
Не всегда делится. Случаи, когда нет делимости на 3, расположены через два на третий. Это когда нечётное число само делится на 3 — мы это уже увидели при анализе числа 3. И что интересно, в этих случаях результат делится на 8. Еще одна закономерность в качестве гипотезы.
А когда число не делится на 3, то результат делится на 3 независимо от простоты.
UPD утром. А проверим чётные n:
2² – 1 = 3 — делится;
4² – 1 = 15 — делится;
6² – 1 = 35 — не делится;
8² – 1 = 63 — делится;
10² – 1 = 99 — делится;
12² – 1 = 143 — не делится;
14² – 1 = 195 — делится;
16² – 1 = 255 — делится;
18² – 1 = 323 — не делится;
20² – 1 = 399 — делится;
22² – 1 = 483 — делится;
24² – 1 = 575 — не делится...
Так что нечётность тут роли не играет. В связи с этим мне придётся внести дальше исправления.
Нет, немного играет. В чётном случае, если результат не делится на 3, то делимости на 8 нет (результат вообще нечётный).
Конечно, это пока просто наблюдения. Необходимо
Доказательство
Если число n не делится на 3, то оно имеет вид n = 3k ± 1. (А чтобы n оказалось нечётным, нужно, чтобы 3k было чётным. А это значит, что число k четное. Впрочем, это для доказательства оказалось ненужным. См. выше UPD.)
Вычисляем:
n² – 1 = 9k² ± 6k + 1 – 1 = 9k² ± 6k = 3(3k² ± 2k) делится на 3.
Первая часть гипотезы доказана.
Теперь пусть нечётное n делится на 3: n = 3k. Тогда
n² – 1 = (3k)² – 1 = (3k – 1)(3k + 1).
Так как k нечётно, то множители (3k – 1) и (3k + 1) суть два последовательных чётных числа. А это ещё в детстве было известно, что из двух последовательных чётных чисел одно делится на 4, а другое только на 2. Поэтому n² – 1 делится на 4 ∙ 2 = 8.
Замечание о двух последовательных чётных числах. Они получаются удвоением двух последовательных целых. А одно из них обязательно чётно, а другое нечётно. Удвоив, получаем одно делящееся на 4, а другое только на 2.
UPD 2 на следующий день. Во второй части делимость на 3 несущественна. В самом деле, для нечётного n число n² – 1 = (n – 1)(n + 1) есть произведение двух последовательных чётных чисел. Отсюда поправка в формулировке теоремы.
Вывод
Так что всё оказалось просто. Простота чисел здесь не при чём. Важна нечётность. Заодно нашли еще делимость на 8. Окончательная формулировка:
Теорема. Если n не делится на 3, то n² – 1 делится на 3. Если нечётное число n делится на 3, Если число n нечётно, то n² – 1 делится на 8.
Лень
Надо бы встать и записать это всё. Но в постели так приятно! Отложил до утра.
Продолжение на следующий день
Ну, раз делится на 8, то давайте поделим. Перепишем первую таблицу экспериментов в новом виде:
(3² – 1) / 8 = 1;
(5² – 1) / 8 = 3;
(7² – 1) / 8 = 6;
(9² – 1) / 8 = 10;
(11² – 1) / 8 = 15;
(13² – 1) / 8 = 21;
(15² – 1) / 8 = 28;
(17² – 1) / 8 = 36;
(19² – 1) / 8 = 45;
(21² – 1) / 8 = 55;
(23² – 1) / 8 = 66;
(25² – 1) / 8 = 78;
(27² – 1) / 8 = 91...
Какие знакомые числа справа от знака равенства! Ах, да! Они получаются суммированием всех натуральных от 1 до данного:
1 = 1;
1 + 2 = 3;
1 + 2 + 3 = 6;
1 + 2 + 3 + 4 = 10...
До какого такого данного? До того, из которого n получается по формуле
n = 2k + 1.
А по формуле суммы членов арифметической прогрессии, эта сумма равна
k(k + 1) / 2.
Итак, если n = 2k + 1, то
n² – 1 = 8 ∙ k(k + 1) / 2
(сокращать 8 и 2 я не стал, чтобы было видно, что сомножитель к 8 есть целое число). Или, иначе, если n нечётно, то
n² – 1 = 8 ∙ k(k + 1) / 2, где целое k = (n – 1) / 2.
Доказывается простым подсчётом:
n² – 1 = (2k + 1)² – 1 = 4k² + 4k = 4 ∙ k(k + 1).
Теперь результаты удобно сформулировать в виде двух отдельных теорем.
Теорема 1. Если n нечётно, то n² – 1 = 8 ∙ k(k + 1) / 2, где целое k = (n – 1) / 2.
Следствие. Если n нечётно, то n² – 1 делится на 8.
Теорема 2. Если n не делится на 3, то n² – 1 делится на 3.
Заключение
Это не более чем школьная математика. Не выходит за рамки школьного образования.
А я решил на таком примере "исследования" показать три вещи:
- Движение от наблюдения к гипотезе, а затем, через анализ, к доказательству теоремы.
- Каким извилистым может быть путь к окончательному результату.
- Даже при таком элементарном материале его чтение (понимание) может требовать определённых умственных усилий.