Если я буду перечислять всё, о чём эта статья, вы не будете её читать. А вообще она о моём исследовании

Вот это нихуя себе, я сел писать статью. Сам! И о чём таком интересном могу писать Я? Конечно же, о СЕБЕ!

В ВУЗе какая-то невъебенная нагрузка, я думал, что когда студенты говорят, что ЕГЭ — ничто по сравнению с учёбой в университете, они преувеличивают. Похоже, не преувеличивают. С другой стороны, действительно ощущается рост уровня в математике и программировании.

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

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

Короче, сегодня у нас много материала и я, пожалуй, начну.

Немножко из теории групп.

— Какая нахуй теория групп, мы че тут сммщики, чтобы группы изучать? — зададите корректный вопрос вы.

А на самом деле группы — это не паблики (я серьёзно, между ними есть разница) и даже не куски потока.

Группа — это множество всяких штук, чаще — чисел, для которых определена какая-то операция между двумя элементами и, используя эту операцию, вы всегда в результате получите элемент этого же множества. Кроме того, если вы примените операцию, обратную данной, вы всё равно получите элемент из этого множества. И, последнее, должен быть элемент, нейтральный относительно этой операции. Обратный сам себе.

Уподоблюсь своим редакторам. И приведу по возможности понятный и реальный пример.

Пусть у нас есть множество из трёх элементов: Никита (Н), яйцо (я) и яйцеНикита (Ня). Определим операцию яйцезации. И будем обозначать её знаком «0». Это не ноль, это знак операции, как «+», «-», «/» и т.п.

Итак, определим операцию яйцезации следующим образом:

Н 0 я = я
Н 0 Ня = Ня
Н 0 Н = Н
Ня 0 я = я
Ня 0 Ня = Ня
Ня 0 Н = Ня
я 0 я = я
я 0 Ня = я
я 0 Н = я

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

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

Дальше мы можем заметить, что у нас операция коммутативная. Что это значит? Это значит, что если мы поменяем элементы справа и слева от 0, результат не изменится. Коммутативными операциями являются, например, сложение и умножение, хоть и не всегда, но об этом мы поговорим после.

Кроме всего прочего, у нас есть нейтральный элемент. Нейтральный элемент в данном случае — Никита, потому что с чем его ни яйцезируй, всё равно получится то же, что было в начале. Нейтральным элементом относительно умножения является 1, а относительно сложения — 0. Здесь это ноль, а не яйцезирование.

Что происходит дальше? Дальше мы хотим проверить, ассоциативна ли наша операция. Яйцезация ассоциативна, если для неё верно
А 0 (B 0 C) = (A 0 B) 0 C

Ну, очевидно, яйцезация ассоциативна, потому что в любом случае в результате применения мы получим наиболее яйцезированное из А, В, С.

Отлично. На самом деле, с этим никогда проблем не бывает. Проблемы начинаются, когда мы вводим операцию, обратную данной. Я не знаю, как мы её назовём, но обозначать будем так: «8».

Операция 8 такая, что:
(А 0 B) 8 B = A

То есть она просто берёт и выкидывает второй элемент. Ну давайте посмотрим, как она у нас сработает:

Как вы видите, тут у нас всё сломалось. Операция «8» не определена, потому что для пары одних и тех же чисел она возвращает разные значения. Плохая операция, не хорошая. А на самом деле, нам просто не повезло с яйцезацией.

Ну раз уж у нас не вышло с яйцами и Никитами, перейдём к более известному множеству натуральных чисел и более понятной операции сложения.

Если мы возьмём два натуральных числа и сложим их, мы получим натуральное. Значит, есть подозрение на то, что это группа относительно сложения.

Сложение ассоциативно:
1+(3+5) = (1+3)+5

Если предполагать, что 0 включён в множество натуральных, то у нас есть и нейтральный элемент относительно сложения: A+0 = A.

Вот только с обратной операцией у нас проблемы. Мы не знаем, как вычитать из меньшего большее. Значит, натуральные числа — не группа.

Проблема решается введением множества целых. Множество целых — группа относительно сложения.

Вдобавок ко всему, сложение — коммутативная операция:

1+3 = 3+1

Говорят так: «Во множестве целых чисел существует коммутативная, или абелева (это одно и то же), группа относительно в сложения».

Аналогично, в положительных рациональных числах существует абелева группа относительно умножения.

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

Непустое множество с заданной на нём бинарной (то есть для двух элементов) операцией, результат применения которой возвращает элемент этого множества, называется группой, если выполнены аксиомы:

1. Ассоциативность: (1+3)+5 = 1+(3+5); (1*3)*5 = 1*(3*5);
2. Наличие нейтрального элемента: 0+3 = 3; 1*3 = 3;
3. Наличие обратного элемента: 3+(-3) = 0; 2*(½) = 1

Надеюсь, понятно.

4. Если данная операция коммутативна, то группа называется абелевой.

Кольца

Добро пожаловать в дворец бракосочетаний! Сейчас мы будем женить группы. Но кольцо у нас одно, поэтому и группа в кольце будет только одна.

От метафор перейдём к математике. Честно, я хз, кто дал всем этим штукам такие ебнутые названия, но они есть, и про них можно шутить.

Что такое кольцо в алгебре? Это множество, в котором существует абелева группа относительно сложения (а это мы разобрали выше). Кроме того, в нём определено умножение, и оно ассоциативно. И, самое главное, существует дистрибутивность умножения относительно сложения:

a*(b+c) = ab + ac
(b+c)*a = ba + ca

Обратите внимание, о коммутативности умножения здесь речи не идёт, то есть две штуки, написанные выше, могут быть и не равны друг другу.

Итак, кольцо это:

1. Абелева группа по сложению
2. Почти группа по умножению, но необязательны наличие нейтрального элемента и наличие обратных элементов. Говорят «полугруппа», но это довольно расплывчатое понятие

Таким образом, множество целых чисел — уже кольцо.

Множество положительных рациональных — не кольцо, так как в нём нет группы относительно сложения.

Кольца прикольны тем, что умножение может быть не коммутативно. Такое бывает, например, когда мы берём произведение векторов. Векторное произведение не коммутативно, однако множество всех векторов всё равно остаётся кольцом. Для этого в алгебре придумали какие-то более сложные штуки, вдаваться в подробности не будем.

Поля

Ну охуеть, теперь мы идём выращивать картошку.

Полем в математике называется кольцо, которое кроме всего прочего ещё и абелева группа по умножению. И вот тут уже появляется некоторая логика в названиях. Кольцо это поле, из которого выбили серединку — ту часть, которая связана с делением. Но иногда не выбили. Ведь поле без дырок это тоже кольцо.

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

Тем не менее, всё достаточно просто:

группа → кольцо → поле

И вот эти 7 или 8 аксиом, на которых строится поле, по сути основа всей той алгебры, с которой нам приходилось работать в школе.

Потому что вещественные числа — это поле. И многие свойства вещественных чисел доказываются именно через аксиомы поля.

Самое простое поле, кстати, это поле рациональных чисел. Обратите внимание, что в рациональные числа входит 0. 0 — это элемент, нейтральный относительно сложения. Но кроме прочего, это элемент, который не имеет обратных по умножению.

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

Кстати, есть ещё другое понятие — тело. Тело это почти поле, но умножение может быть не коммутативно.

Надеюсь, не сильно сложно.

Небольшая разминка

Давайте теперь вернёмся к яйцам и Никитам. И попробуем ввести новую операцию 0 такую, чтобы у нас наше множество получилось хотя бы группой.

У нас есть Н, я и Ня. Пусть Н — нейтральный элемент. Тогда:

Н 0 я = я
Н 0 Ня = Ня
Н 0 Н = Н

Причём применение операции к нейтральному элементу коммутативно, поэтому получим ещё два свойства:

я 0 Н = я
Ня 0 Н = Ня

Если Н нейтральный элемент, то два оставшихся должны быть обратны друг другу:

Ня 0 я = Н
я 0 Ня = Н

Таким образом, нам не хватает всего двух случаев:

Ня 0 Ня — ?
я 0 я — ?

Чтобы их определить, воспользуемся аксиомой ассоциативности:

Ня 0 (Ня 0 я) = (Ня 0 Ня) 0 я
Ня 0 Н = (Ня 0 Ня) 0 я
Ня = (Ня 0 Ня) 0 я

Если взять Ня 0 Ня равным Н, то тогда мы получим Ня = я, что, в принципе, возможно, но нежелательно. Есля взять Ня 0 Ня = Ня, то получится Ня = Н, тоже не очень. Остаётся лишь вариант Ня 0 Ня = я. И тогда я 0 я = Ня. Прекрасно.

Чтобы нам разминаться дальше, давайте скажем, что у нас 0 это не просто какая-то непонятная операция, а СЛОЖЕНИЕ. Вот так вот. Сумма яйцеНикиты и яйца равна Никите. Обдумывайте.

И тогда у нас:

Н+Н = Н
Н+Ня = Ня
Н+я = я
Ня+Н = Ня
Ня+Ня = я
Ня+я = Н
я+Н = я
я+Ня = Н
я+я = Ня

Вот такая вот вполне себе православная операция сложения яиц и Никит.

Предлагаю вам доказать, что такая операция ассоциативна, самостоятельно. Или просто поверить мне на слово. Нейтральный элемент у нас есть. Обратные элементы есть у каждого. Значит, мы имеем дело с группой относительно сложения.

Сложение у нас получилось коммутативное, значит, группа абелева.

Теперь введём для данного множества операцию умножения.

Мы хотим получить кольцо. Я не сказал? Мы хотим получить кольцо. Поэтому умножение должно быть ассоциативным. При этом наличие обратных элементов необязательно, но в нашем случае будет А ещё должно быть дистрибутивным относительно сложения.

В приличном обществе умножение отличается от сложения. Или нет? Попробуем определить, отталкиваясь от ассоциативности и дистрибутивности. Коммутативность необязательна, но, возможно, неизбежна.

Итак,
A*(B*C) = (A*B)*C
A*(B+C) = A*B + A*C
(B+C)*A = B*A + C*A

С дистрибутивностью, пожалуй, проще, так как мы знаем суммы всех наших элементов.

Сейчас нам важно доказать, что ноль, то есть Н — нейтральный элемент относительно сложения, является поглощающим элементов относительно умножения. «Что не умножай на 0, получишь 0». Звучит очевидно, но нам необходимо доказать это опираясь лишь на аксиомы кольца.

Для этого в выражение
A*(B+С) = A*B + A*C

подставим С = Н
A*(B+Н) = A*B + A*Н
A*B = A*B + A*Н
Н = А*Н

И аналогично,
(B+Н)*A = B*A + Н*A
B*A = B*A + Н*А
Н*А = Н

Выходит, что любое умножение на Н даёт Н, причём умножение с Н коммутативно. Имеем 5/9 операций:
Н*Н = Н
Н*Ня = Н
Н*я = Н
Ня*Н = Н
я*Н = Н

Остаётся определить
Ня*я — ?
Ня*Ня — ?
я*Ня — ?
я*я — ?

Ну давайте попробуем сделать так:
Ня*(Ня+я) = Ня*Ня + Ня*я
Ня*Н = Ня*Ня + Ня*я
Н = Ня*Ня + Ня*я

Значит, Ня*Ня и Ня*я обратны.

С другой стороны,
(я+Ня)*я = я*я + Ня*я
Н*я = я*я + Ня*я
Н = я*я + Ня*я

Выходит,
я*я + Ня*я = Ня*Ня + Ня*я
я*я = Ня*Ня — одно и то же, получается

И ещё одно:
я*(Ня+я) = я*Ня + я*я
Н = я*Ня + я*я
я*я + Ня*я = я*Ня + я*я
Ня*я = я*Ня — выходит, умножение коммутативно в принципе

Таким образом, умножение у нас коммутативно. Здорово, больше свойств богам свойств!

Остаётся определить лишь
я*я

Причём сделать мы это, похоже, можем любым удобным образом. Не будет особой разницы, чему равно я*я — яйцу или яйцеНиките. Немного другая ситуация — когда это равно Никите. Если это равно Никите, то и все неизвестные нам операции будут равны Никите и умножение всегда будет возвращать Никиту. Это немного странно.

Предлагаю тогда сказать, что произведение яиц даёт яйцо.

я*я = я
Ня*Ня = я
я*Ня = Ня
Ня*я = Ня

Можете доказать сами. Можете поверить. Выше сказано всё необходимое для таких выводов.

А теперь внимание! Сейчас будет фокус. Выпишем все операции умножения, что у нас есть:

Н*Н = Н
Н*Ня = Н
Н*я = Н
Ня*Н = Н
Ня*Ня = я
Ня*я = Ня
я*Н = Н
я*Ня = Ня
я*я = я

Если убрать все операции с нулём Н, заметим, что я — нейтральный относительно умножения элемент. «Единица». А элемент Ня обратен сам себе. Выходит, мы имеем группу по умножению для всех элементов кроме нуля! А, значит, штука, которая у нас получилась — поле. Вот это да! Значит, поле бывает не только бесконечным множеством, как вещественные числа, но и вполне себе небольшим, из трёх элементов.

Кольца вычетов и поля характеристики

А теперь самое интересное. Мы уже знаем, что Н — это 0, я — это 1, а Ня — элемент, обратный я относительно сложения. Тогда поменяем все буковки на циферки и получим удивительную штуку:

0*0 = 0
0*(-1) = 0
0*1 = 0
(-1)*0 = 0
(-1)*(-1) = 1
(-1)*1 = -1
1*0 = 0
1*(-1) = -1
1*1 = 1

Вот это да! Всё как у человеков. А что там по сложению?

0+0 = 0
0+(-1) = -1
0+1 = 1
(-1) + 0 = -1
(-1) + (-1) = 1
(-1) + 1 = 0
1 + 0 = 1
1 + (-1) = 0
1 + 1 = -1

Вас, возможно, смутит то, что я выделил жирным. Дело в том, что мы, по сути, воссоздали кольцо вычетов по модулю 3, или кольцо характеристики 3. Что это значит?

Кольцо вычетов по модулю n это множество всех возможных остатков при делении на число n. Или, ещё проще говоря, это все числа от 0 до n-1. Но последнее не совсем то.

В общем, представьте часы. На них 12 делений. И 7+8 = 3. Часы — это кольцо вычетов по модулю 12. Всё, что делится на 12 — это 0. Поэтому в кольцах вычетов всегда много нулей. И могут быть делители нуля: например, 3 и 4 делят 12, значит, это делители нуля.

Кольцо характеристики 3 содержит три элемента: 0, 1, 2. Однако для кольца вычетов по модулю 3 числа -1 и 2 будут одинаковы, ведь -1+3 = 2.

Отсюда и появляется это 1+1 = -1.

Кольцо, характеристикой которого является простое число, не содержит делителей нуля. И за счёт этого является полем. Это сложно объяснить, но можно показать.

Возьмём кольцо по модулю 12. В нём делители нуля: 2, 3, 4, 6. Найдём число, обратное числу 8 по умножению.

А ЕГО НЕТ!

Потому что на что в данном случае результат умножения числа 8 на что-либо будет чётным, так как модуль чётный. А 1 — необходимый результат умножения — нечётное.

Если же мы рассмотрим кольцо характеристики 11, то для каждого числа кроме нуля найдём обратное по умножению.

1*1 = 1
2*6 = 12 = 11+1 = 1
3*4 = 12 = 11+1 = 1
4*3 = 12 = 11+1 = 1
5*9 = 45 = 44+1 = 1
6*2 = 12 = 11+1 = 1
7*8 = 56 = 55+1 = 1
8*7 = 56 = 55+1 = 1
9*5 = 45 = 44+1
10*10 = 100 = 99+1 = 1

Ну и в принципе выполняются аксиомы поля. И это прекрасно, и этим надо пользоваться.

Поле комплексных чисел

Сейчас я вас всех удивлю, особенно тех, кто разбирается в теме, но эта статья, вообще-то, о теории чисел. Одним из мощнейших инструментов современной теории чисел наравне с кольцами вычетов являются гауссовы целые числа, особенно когда дело касается сумм квадратов.

Гауссовы числа — это обобщение целых чисел на поле комплексных чисел. А про комплексные числа я писал пару месяцев назад, но так и не написал. Поэтому объясню в этой статье.

Каким-то очень наглым людям очень понадобилось брать корни от отрицательных чисел. Перебрав пару миллиардов моделей для сложившейся ситуации, эти очень наглые люди не нашли ничего лучше, чем придумать новую единицу. Мнимую. Обозначается как i. Такую единицу, что
i*i = -1

Вы, наученные опытом предыдущих пунктов, завопите и скажете: ООООООООООООООООООО, ЭТО ЖЕ 2, ЕСЛИ БРАТЬ ПОЛЕ ХАРАКТЕРИСТИКИ 5.

Но у нашего поля нет характеристики. Да и вообще мы пока говорим не про поле.

В общем-то, теперь, когда появилась мнимая единица, стало возможно записывать корни любых отрицательных чисел. Например, 2i это корень из -4. Вполне понятно. На английском такие числа называются «воображаемые». Но воображаемые они лишь до тех пор, пока не возведёшь их в квадрат.

Оказалось, что складывать мнимые числа с действительными не очень-то удобно, и пришлось изображать их сумму на плоскости. z = x+yi — типичное комплексное число. Комплексует в двухмерном измерении, в то время как действительные числа вполне себе обходились одномерным.

Проблема, а может быть достоинство комплексных чисел в их неоднозначности. Например, уравнение
z³ = 27

будет иметь в комплексных числах не одно, а три решения. Почему? Потому что
(x+yi)³ = 27
x³ + 3x²yi - 3xy² - y³i = 27 + 0i

x³-3xy² = 27
3x²y - y³ = 0

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

Чтобы не решать такие неприятные системы, люди придумали использовать для комплексных чисел полярную систему координат. Вместо х и y в этой системе r — расстояние от начала координат, и φ — угол, под которым нужно провести прямую из начала координат, чтобы данная точка лежала на этой прямой.

На самом деле, r = √(x²+y²), — по теореме Пифагора, а φ — арктангенс y/x. И, наоборот,
x = rcosφ
y = rsinφ

И выяснилась удивительная штука. Сейчас покажу:
(x+yi)² =
r²(cosφ+isinφ)² =
r²(cos²φ - sin²φ + 2icosφsinφ) =
r²(cos2φ + isin2φ)

И это работает для любой степени. В тригонометрической форме такие уравнения решаются легче. Намного легче.

Есть ещё экспоненциальная форма записи , но сейчас не о том.

Прикольно то, что поле комплексных чисел — поле. Доказывать я это, конечно, не буду, но если интересно, почитайте Винберга. Прям так и пишите в гугл: «Винберг, алгебра», и он вам выдаёт книжку Винберга. Говорят, там неплохо объяснены начала линала, но я не дочитал.

Кстати, доказать вы можете и сами. Хотя почитать всё равно советую.

Ну а мы идём дальше.

Гауссовы целые числа

Да. Эта та штука, для которой я вам объяснил комплексные числа, и которая никак не пригодится для этой статьи. Я серьёзно. Я не знаю, зачем я это сейчас пишу. Но пишу и буду писать.

Гауссовы числа это числа вида a+bi, где a и b целые. Обобщение для целых. Так же как и в нормальных целых, в гауссовых целых есть простые числа. И, внимание, сейчас будет шок. 5, 13, 17, 29 и другие простые вида 4k+1 не являются простыми гауссовыми числами. Почему? Потому что они представимы в виде суммы квадратов. Почему? Не помню. Но там что-то Ферма с Эйлером сделали и доказали. Или не они. Может быть и сам Гаусс, он вообще большой вклад в тч внёс.

Так, а почему если эти числа представимы в виде суммы квадратов, они не простые?

Примерно по той же, по которой многие разности квадратов не простые, но если там это было не точно:
2²-1² = (2-1)(2+1) = 1*3

То для суммы квадратов это всегда так:
2²+1² = (2+i)(2-i) = (1+2i)(1-2i)

Самое удивительное, что сумму квадратов очень легко найти, зная разложение числа на простые множители.

Как ещё похвалить гауссовы числа? Ну заебатые такие числа, пиздатые, решили немало проблем математики.

Если интересно, про них удивительно понятная статья на Википедии.

А мы снова идём вперёд. И чего-то давно в тексте не было картинок. Надоело читать один сплошной текст?

И снова к кольцам вычетов… Функция Эйлера

И в статье у меня какой-то салат, и вряд ли понятно к чему я веду, потому что чтобы нормально водить, надо отучиться на права, а я так и не доучился.

Как думаете, сколько функций названо в честь Эйлера? Не поверите, всего одна. Что же за функция, достойнейшая из достойнейших?

Это функция, которая возвращает количество чисел, взаимно простых данному меньше него.

Ну, типа, 6 взаимно просто с 1 и 5, поэтому функция Эйлера от 6 будет равна 2. Функция Эйлера обозначается буквой фи. фи. φ. Ну вы поняли.

Очевидно, для любых простых p, φ(p) = p-1. Ну потому что не взаимно простое с p только кратное p. А кратных p меньше p нет.

φ(1) = 0

Для остальных чисел функцию Эйлера можно посчитать по свойствам. Самое простое из них — φ(a*b) = φ(a)*φ(b) — функция Эйлера мультипликативна.

Хочу отметить, что в теории чисел мультипликативность определяется только для взаимно простых чисел. Если a и b взаимно просты, это свойство работает. Для не взаимно простых — не работает.

В других разделах математики, как правило, функция f(x) мультипликативна, если f(x*y) = f(x)*f(y), для любых x, y.

И ещё свойство:

Зная то, что я написал выше, можно найти функцию Эйлера от любого числа. И без каких-либо проблем вывести общую формулу, связанную с разложением числа на простые множители.

Выбирайте любой вид, они все используются.

А теперь вопрос. Зачем нам это надо? Возьмём всем вам любимое кольцо характеристики 10, на котором, в некотором смысле, построена десятичная система счисления.

Такое кольцо содержит 10 элементов:
0 1 2 3 4 5 6 7 8 9

2 и 5 — делители нуля. 4, 6 и 8 делятся на делители нуля. 0, он же 10, — сам нуль.

Числа 1, 3, 7, 9 взаимно просты с нулём. Давайте составим для них таблицу умножения в кольце характеристики 10. В этой таблице, чтобы было понятнее, будут стоять последние цифры от результата их обычного умножения, потому что по сути мы везде берём остаток от деления на 10.

Удивительно, но числа 1 3 7 9 в кольце характеристики 10 образуют абелеву группу по умножению. Вы же это видите?

Не выходят из этого порочного круга общения между собой. Что же будет, если мы возьмём все 10 элементов?

Посмотрите, как много нулей. Много нулей и, если мы, например, на рандоме возьмём столбики 1 2 3 5 9, то это будет даже близко не группа. Многие результаты умножения выходят за пределы множества. Например, 2*3 = 6, но 6 у нас нет.

С другой стороны, группу между собой образуют 2 4 8 6. Или, например, отдельный элемент 5. То есть мы можем выделить отдельные группы элементов, но не можем взять их все вместе.

Так вот какая штука.

2+5 = 7
4+5 = 9
6+5 = 1
8+5 = 3

Наибольшую важность всё-таки имеет группа 1 3 7 9.

Я это к чему? Наверное, к тому, что число, возвращаемое функцией Эйлера, совсем не случайно.

Теорема Эйлера

А вот теорем в честь Эйлера названо дохера. Мы поговорим про ту, которая связана с функцией Эйлера.

Выглядит она так:

Переведу на тот язык, на котором мы с вами говорили выше. В кольце характеристики b любое взаимно простое c b число a, возведённое в степень φ(b) равно единице.

Вот это тройное равно вместе со словом mod означает «сравнимо по модулю», что можно трактовать как «что-то одно имеет такой же остаток от деления на что-то другое, как и что-то третье». Это модульная арифметика, которая занимается примерно тем же, чем мы с вами занимаемся сейчас, только называет это другими словами.

Если говорить о кольце характеристики 10, то:

1^4 = 1
3^4 = 1
7^4 = 1
9^4 = 1

Почему это так? Объясню довольно интуитивно, потому что строго мне лень.

Мы уже выяснили, что не делители нуля образуют группу по умножению. Значит, если мы возьмём, скажем, 3, и будем умножать его на само себя некоторое количество раз, мы сможем прийти только к 3, 9, 7 или 1. При этом, если мы попадём в какое-то из них снова, то дальше всё начнёт повторяться. Значит, до тех пор как мы вернёмся в 3, мы можем побывать в любом другом из четырёх не больше одного раза. И если всего у нас вариантов 4, то как минимум на 5 шаге мы вернёмся к 3. Ну, 3^5 = 3. Если теперь разделим всё на 3, получим 3^4 = 1. Вот.

Пока писал, нашёл в своём интуитивном доказательстве как минимум три неточности, но в принципе звучит логично.

Вы можете заметить, что для 9 есть число меньше функции Эйлера, возвращающее 1. 9² = 1. Поэтому можно сказать, что функция Эйлера — наименьшая гарантированная степень, но для некоторых чисел могут быть степени и меньше.

Я это к чему. Кольцо характеристики 10 идёт сосать жопу, как и кольцо любой другой составной характеристики.

Функция Эйлера обширно используется в теории чисел и имеет прикладное значение. Шифрование RSA построено отчасти на теореме Эйлера. По теореме Эйлера,

А мы идём дальше.

Малая теорема Ферма

Частный случай теоремы Эйлера — малая теорема Ферма. В честь Ферма названо тоже много теорем, но у них хотя бы есть какое-нибудь эпичное слово в названии, типа «малая» или «великая». Наверное, это две его единственные теоремы… Но в честь него названо ещё много лемм и всяких других штук.

Ну и в целом Ферма был очень крутой и, с учётом того что жил он до Эйлера и был самоучкой. И несмотря на то, что Эйлер пришёл и затмил, развил и доработал все математические достижения предшественников, мы помним и любим не только Великую теорему Ферма, но и в достаточной степени важную малую теорему Ферма, которая записывается так:

Думаю, здесь у вас никак проблем не возникнет, тем более что мы уже разобрали теорему Эйлера.

Так вот если мы возьмём p = 5 и построим таблицу умножения

то увидим, что у нас все элементы кольца, кроме 0, образуют группу по умножению. Это даёт нам возможность последовательно умножая элемент на что-нибудь пройтись по всем элементам кольца. И, как я уже говорил, наше кольцо — поле. Поле характеристики или, как ещё говорят, конечное поле.

В таком прекрасном поле можно и поваляться.

Но валяться мы будем в системе счисления по основанию 5. Идём дальше.

Как это всё связано с моим исследованием?

Хотя если вы разбирались в моём исследовании в прошлых статьях хотя бы поверхностно, то вряд ли у вас должен был остаться такой вопрос. Но будем честны: вы не разбирались. Поэтому введу в краткий курс дела.

Последняя цифра числа при возведении в степень циклится. Так, если мы будем 2 в разные степени, то получим:
2 4 8 16 32 64 128 256 512 1024…

Если же обращать внимание только на последнюю цифру, то получим
2 4 8 6 2 4 8 6 2 4

Это, на самом деле, доказывается двумя фразами: «последняя цифра произведения зависит лишь от последней цифры множителей» и «32 заканчивается той же цифрой, что и 2».

Более того, повторяется не только одна цифра, но и последние две, последние три и так далее… Только реже. Вопрос — насколько реже. И зачем?

В десятичной системе счисления не всё так просто, поэтому я написал код (ещё до тех пор, как поступил туда, где меня сейчас учат писать код), который строит таблицы для моего исследования в различных системах счисления. Чтобы было понятнее, построю таблицу в десятичной системе для числа 2, будем рассматривать последние 5 цифр степени:

Не очень сильно ругайтесь на оформление, я писал это давно. Что вы здесь видите? В принципе, всё, что нужно. В столбцах везде совпадают последние цифры. Выделяется 00001. В блоках совпадают две последние цифры. Номер это степень, в которую мы возводим. 4+3, 8+2 — это степени.

Для удобства, я сделал возможность отображения не всех столбцов, а только n первых. Так, я могу сделать таблицу более широкой, но более интересной

Здесь повторяться будут последние две цифры в столбце и последние три в блоке. Но эта таблица не покажет нам степени типа 20k+10, 20k+15, 20k+17 и в принципе +что-либо больше 9 и меньше 20.

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

Беды, вообще-то, видно уже здесь. Выделю их красненьким

В общем, все столбцы как столбцы, но первые три решили повыёбываться и как-то не так зациклились. Мы как бы ждали 01, а получили 76, неприятно. Ждали 02, а получили 52. Ждали 004, получили 504. Такая штука продолжится и дальше. Так, если мы рассмотрим 500 степеней, то в тот момент, когда нам будет нужно 0008, у нас появится 5008 ну и так далее. Почему? Ну, потому что в кольце вычетов характеристики 10 у нас
2*5 = 2*0

Это так, потому что 2 — делитель нуля. Думаете, на этом беды десятичной системы закончились? Нет. Казалось бы, для чисел на 1, 3, 7, 9 всё должно быть прекрасно, они же образуют абелеву группу по умножению и ещё они взаимно просты с 10.

Вот возьмём обычное такое всем понятное число 13 и посмотрим, что с ним произойдёт. Сначала с одной цифрой

Всё заебись, период зацикливания 4, иначе и не могло быть по теореме Эйлера. 13, всё-таки, взаимно просто с 10.

Теперь с двумя:

Период зацикливания для двух последних цифр — 20. Ну раз так, то давайте просто каждый раз умножать количество столбцов на 5 и смотреть, что выйдет.

Всё хорошо, последние три цифры циклятся раз в 100 степеней.

Четыре цифры циклятся раз в 500 степеней, всё закономерно. Очевидно, теперь пора взять 2500

Ну вот и что это за херня? Всё было так мило, мы шли себе спокойно, умножая всё на 5, и пришли к 2500, а тут такое. Обидно немного, да? Хочу вас успокоить — с этого момента и до конца [его нет] придётся всё умножать на 10.

Ну в принципе как бы и ладно, но как-то всё равно неприятно. Печалит меня эта ситуация со степенями.

Поэтому я решил вырваться на свободу и пойти исследовать все эти свойства в их первозданном виде. В системе счисления по простому основанию. По основанию 5.

Вам, на самом деле, сейчас будет немного больно, потому что система счисления по основанию 5 немножко непривычная. Я буду говорить вам «смотрите, это арифметическая прогрессия», а вы будете смотреть на меня и думать, что я долбоёб. В принципе, классическая ситуация, люблю так делать с Нерегулярным автором.

Итак, готовы?

Идём в простой народ.

Прежде чем начать строить таблицы, давайте подумаем, а когда у нас начнёт повторяться последняя цифра. Думать, на самом деле, долго не придётся. По малой теореме Ферма всё что угодно в 4 степени даст 1 по модулю 5.

Мне почему-то очень нравится число 13, поэтому я использую его и здесь. Кстати, 13 в 5-чной системе счисления — это 23.

А потом всё умножим на 5.

Милота, да? Почему милота? Потому что я сказал коду, что у меня будет всего 4 столбца, но ещё попросил отображать его первые 8 столбцов, а не 4. А код этот, на самом деле, говно. И когда он мне несколько минут назад предложил поесть говна, он, похоже, намекал на себя. Ну вот сейчас я поел говна.

Забудьте то, что было на картинке выше, и смотрите сюда:

Хотя тут мало цифер. Хочу больше цифер, чтобы лучше объяснять.

Смотрите, арифметические прогрессии! Круто, да? Ладно, на самом деле, вы их не видите. Хотя может видите и придуриваетесь.

Сразу внесу ясность — это прогрессии по модулю, ну, то есть, мы отрезаем последние четыре цифры от чисел и видим, что они образуют прогрессию.

Вот так:

В первом столбце я выделил последние две цифры. Они образуют арифметическую прогрессию нулевого порядка. Во всех столбцах, не только в первом.

Во втором столбце я выделил последние четыре цифры. Они образуют арифметическую прогрессию второго порядка. Вы можете заметить, что здесь все числа отличаются на 100. Вторую прогрессию образуют последние четыре цифры во всех столбцах, не только во втором.

В третьем столбце я выделил последние 6 цифр. Они образуют прогрессию второго порядка. И тут вы мне пока что просто поверите.

Ну и в четвёртом столбце я выделил последние 8 цифр. Прогрессия третьего порядка.

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

Я обещал вас научить вычитать в пятеричной системе счисления. Точнее, прямо сейчас обещаю и прямо сейчас научу. Давайте мы из числа 4110042 вычтем 431142.

Нам сказочно повезло — люди придумали целых 10 цифр, я используем мы тут всего лишь 5. Давайте использовать все 10. Для того чтобы нам без проблем вычесть из большего меньшее давайте сделаем так, чтобы у нас все разряды большего были больше, чем разряды меньшего:

4110042 = 3610042 = 3560042 = 3555042 = 3554542

Теперь вычтем:

4110042 - 431142 =
3554542 - 431142 =
3123400

Вот и всё.

Если бы у нас получилось что-то типа
3123600, то мы бы сделали так:
3123600 = 3124100 и, тем самым, свели бы к каноническому виду пятеричной записи. В общем, я думаю, тут проблем нет.

Пользуясь прекрасным методом вычитания в пятеричной системе счисления, мы с радостью получим, что последовательность чисел из третьего столбца является арифметической прогрессией второго порядка:

13434 - 1134 = 12300
41234 - 13434 = 22300
124034 - 41234 = 32300

32300 - 22300 = 10000
22300 - 22300 = 10000

Прелесть. Чтобы не заниматься такой хернёй самому, я написал не менее хуёвый код-калькулятор для пятеричной системы счисления. Но он со своими задачами справляется, так что всё хорошо.

Ещё написал генератор арифметических прогрессий в пятеричной системе и он тоже такой нормальный неплохой написан криво но работает.

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

Мы с вами построили таблицу специально так, чтобы последние две цифры в столбцах совпадали. Специально сделали именно 20 столбцов. В первом столбце у нас 13^0 и числа, которые заканчиваются теми же двумя цифрами.

Значит, их разность будет, вы не поверите, будет заканчиваться двумя нулями.

Чтобы не привязывать себя к числу 13 и системе счисления 5, назовём их a и p. Последнее должно быть простым.

Тогда мы можем без проблем объявить такой факт:

Звучит немного мерзко, да?

Ну это, по сути, формальное описание того, что вы видели в таблицах выше.

Доказывать будем? Давайте всё-таки докажем. Сразу предупреждаю, доказательство выглядит страшно и читать его необязательно. Но если вам интересно разбираться вместе со мной, то давайте

Вот мы и доказали очевидный факт. Можем двигаться дальше.

Ещё немножко о функции Эйлера

Попробуем доказать одну штуку, в которой я не до конца уверен.

Выглядит это свойство так:

Для вас, наверное, является новым факт о том, что можно домножать все части в сравнимости на одно и то же число. В этом, на самом деле, нет ничего удивительного, запись
a = b mod c

означает, что
a = ck + b

А в обычных уравнениях можно умножать что угодно на что угодно в большинстве случаев.

Итак, я ещё раз выпишу то свойство, что мы выяснили, и мы начнём обобщать.

Ещё лучше будет, если мы запишем это так:

А теперь обобщение. Ура, сейчас мы обобщим и будем счастливы.

Докажем? Конечно, докажем, и пойдём отдыхать. Читать, как и в прошлый раз, не обязательно, но ниже будет ещё конец статьи, так что не уходите.

Обратите внимание, что если a и b взаимно простые, то n = 0, а, значит, k может быть хоть нулём. Если у b не так много делителей, или, что важнее, не такая большая степень простых, которые входят в её разложение, то мы этого практически не заметим, всё будет очень похоже на случай с простыми.

И я сейчас задумался о том, что вы не очень-то хорошо понимаете, наверное, как связано то, что мы решали, с теми таблицами, что я вам показывал.

Всё очень просто. b это система счисления, в которой мы работаем. a это число, которое мы рассматриваем. x[0] это последовательность одного из столбцов, причём j — номер строки, а k — это номер этого столбца. Все остальные иксы это разности столбцов.

И… пора подводить итоги.

Едва ли вы рады как я, ноооо… Это же вау! Сегодня наконец-то подведены итоги того исследования, с которого практически начинался паблик и которым я занимался 2 года. Бесполезное исследование, вообще-то, но затягивает.

Эта статья — мощнейший труд в истории паблика. Тот труд, который вы не будете читать, ну потому что нахуй оно вам надо. Писал его где-то около месяца. Перечитывать не буду, лениво.

Я пошёл в зимнюю спячку, желаю вам всех благ. Если успею написать статью до Нового года, ждите её 31 декабря.