Маленькие, как правило, умеют меньше больших. Они, конечно, могут залезть в недоступные для больших места, но это сейчас не в счёт.
Все мы знаем и любим целые числа. У них есть куча достоинств! С них начинается арифметика и знакомство маленьких с математикой. Их можно складывать и вычитать, а также перемножать и решать разнообразные уравнения, которые называются диофантовыми. Правда, большие математики их, мягко говоря, недолюбливают, потому что общих методов их решения немного и задачи, которые выглядят простыми, на деле оказываются сверхсложными или почти неразрешимыми.
А если использовать не все целые числа сразу, а только их конечное подмножество? Действуя аккуратно, из них можно соорудить маленькую арифметику. Самые простые из таких арифметик — модулярные арифметики. Они получаются когда мы от числовой прямой переходим к "числовой окружности", разбивая её на равные части, как на циферблате. Если арифметику целых чисел обозначают ℤ, то для арифметик на циферблате с n делениями используется обозначение ℤ/nℤ.
Когда дело касается исчисления времени, мы пользуемся именно такими арифметиками, считая минуты (ℤ/60ℤ), часы (ℤ/24ℤ), месяцы (ℤ/12ℤ) и дни недели (ℤ/7ℤ). Цифры, которые мы используем в позиционной системе счисления тоже образуют конечную арифметику ℤ/10ℤ. А компьютерщики используют двоичное счисление, основанное на арифметике с двумя элементами ℤ/2ℤ.
Разумно предположить, что маленькие конечные арифметики окажутся слабее "большой" арифметики ℤ с бесконечным числом элементов. Например, в ℤ/10ℤ нет моего любимого числа 13. Но кое в чём они могут быть и сильнее.
Во-первых, таких арифметик много — столько же, сколько натуральных чисел, и каждая из них имеет свои особенности, делающие её непохожей на остальные.
Во-вторых, конечные арифметики содержат конечное число элементов, а значит, задачи в них можно решать простым перебором.
Во-третьих, некоторые диофантовы уравнения, которые сложно или невозможно решить в ℤ, могут иметь решения в конечных арифметиках.
Приведём несколько примеров.
Формальные дроби
В арифметике ℤ/5ℤ из пяти элементов {0,1,2,3,4} у каждого элемента есть противоположный, то есть такой, что в сумме они дают ноль. То есть, в этом смысле оно включает в себя и "отрицательные числа":
1 = −4, 2 = −3, 3 = −2, 4 = −1.
Более того, в этой системе у любого корректного линейного уравнения a•x = b, есть решение, которое записывается формальной дробью x = b/a. Таким образом, оно содержит в себе все возможные формальные дроби, не существующие в целых числах:
2 = 1/3 = 3/4, 3 = 1/2 = 4/3, 4 = 1/4 = 3/2 = 2/3.
Вообще, во всякой арифметике ℤ/mℤ с простым m, возможно решение любых линейных уравнений.
Большая теорема Ферма
Большая теорема Ферма, гласит, что в ℤ уравнение xⁿ + yⁿ = zⁿ не имеет нетривиальных решений при n > 2. В то же самое время, в модулярных арифметиках, это уравнение решается. Например, для ℤ/2ℤ, простым перебором легко проверить, что решения есть при n = 3, 4, 5...
Наконец, доказана теорема Шу́ра, утверждающая, что для любого n найдется натуральное число p, такое, что для простого m > p уравнение Ферма решается в ℤ/mℤ.
Корень из минус единицы
Число √−1, решающее уравнение x² + 1 = 0, не существует не только в ℤ, но и в вещественных числах ℝ. Однако, это уравнение решается, например, в ℤ/5ℤ: 2² + 1 = 5 = 0 mod 5.
И вообще, это уравнение имеет решения в арифметиках ℤ/mℤ, где m кратно 2, 5, 13, 17, 29 и т. д. Только не надо думать что 2 это мнимая единица в ℤ/5ℤ, это рядовое число.
Автоморфные числа
А вот ещё один пример числа, не существующего ни в ℤ, ни в ℝ. Это решение уравнения x² = x, отличное от 0 и 1. Такие числа, например, существуют в арифметиках ℤ/10ℤ, ℤ/100ℤ, ℤ/1000ℤ и т.д. Смотрите сами:
5² = 25 = 5 mod 10, 6² = 36 = 6 mod 10,
25² = 625 = 25 mod 100, 76² = 5776 = 76 mod 100
625² = 625 mod 1000, 376² = 376 mod 1000
...
Золотое сечение
Уравнение x² − x − 1 = 0 имеет два иррациональных решения, которые связаны с числами Фибоначчи. Одно из них, положительное, называется золотым сечением ϕ. В ℤ таких чисел нет, а в ℝ, как известно, ϕ = (1 + √5)/2.
Однако это уравнение решается во всех модулярных арифметиках, содержащих √5 (арифметиках ℤ/mℤ, в которых m = ±1 mod 5). Самая простая из них — ℤ/11ℤ, в которой ϕ = 4 и 1/(−ϕ) = 8.
Во всех этих арифметиках можно напрямую использовать знаменитую формулу Бине, которая позволяет в конечной форме вычислить k-ое число Фибоначчи.
О том, почему использовать формулу Бине можно там, где это уравнение не решается (как в ℤ, например) стоит рассказать отдельно.
* * *
Так что крутые малыши могут многое! А ещё они могут расти. Всё, что может арифметика ℤ/mℤ доступно и для арифметики ℤ/mⁿℤ. Но при повышении степени растут и возможности.
Рассмотрим, например, арифметику ℤ/25ℤ. В ней, как и у еë меньшей сестры ℤ/5ℤ, тоже есть все противоположные числа и большая часть формальных дробей (кроме тех, что имеют знаменатель, кратный 5). Имеется в ней и √−1 = ±7, а также появляются корни из ±6 и ±11, которых не могло быть в ℤ/5ℤ. В ещё большей арифметике ℤ/125ℤ остаётся всё то же, что было у еë меньших братьев, но расширяется набор квадратных уравнений, имеющих решения и появляется возможность решать некоторые кубические уравнения.
А интересно, если продолжать наращивать степени и новые возможности, то какими свойствами будет обладать арифметика ℤ/mⁿℤ при n ⟶ ∞? На этот вопрос ответил Курт Гензель, определив для такого предельного случая числовую систему и описав его свойства. Такие системы называется целыми p-адическими числами. Они включают в себя всех своих младших сестëр, как подарифметики и обладают всеми их свойствами сразу! Но об этом надо рассказывать отдельно.
Модулярные арифметики не единственные конечные арифметики, используемые в математике. Исследованием таких арифметик и поиском их сверхспособностей занимаются теория конечных полей и колец.
Больше про модулярные арифметики можно прочитать в серии заметок: