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

элис занимается изготовлением разноцветных сережек из бисера и решила изготовить все возможные виды сережек для каждого возможного размера для начала она решила посмотреть сколько всего различных серёжек можно изготовить из трех бисерин двух цветов каждая сережка начинается с цепочки бисерин концы которой потом сводят в кольцо поэтому первый вопрос сколько можно составить цепочек три бисерины два цвета на каждую позицию можно поставить один из двух цветов получается 2 умножить на 2 умножить на 2 то есть восемь различных последовательностей бисерин затем элис убирает монохромные цепочки состоящий из бисерин одного цвета оставшиеся бисеринки она склеивает в кольцо и ожидает что получится 6 разных сережек но что-то пошло не так некоторые сережки стали неразличимыми оказалось что у нее получилось всего два варианта сережек у каждой сережки обнаружилось по две идентичные копии любую сережку в группе можно получить из любой сережки в той же группе простым поворотом то есть размер группы зависит от того сколько раз можно повернуть сережку до начального положения или другими словами сколько поворотов составляют полный цикл выходит что изначальный набор разноцветных цепочек делятся на две равные группы по три цепочки в каждой верно ли это для других размеров было бы удобно потому что тогда в ассортименте окажется одинаковое количество серёжек каждого стиля элис проделывает все тоже самое теперь только с четырьмя бисеринами сначала она составляет все возможные цепочки четыре позиции на каждой позиции может стоять одна из двух бисерин значит всего вариантов 2 умножить на 2 на 2 умножить на 2 равно 16 затем она снова удаляет 2 монохромной цепочки а из остальных опять склеивает кольца получается ли теперь group и равного размера похоже что нет что же произошло обратите внимание как изначальные цепочки делятся по стилям все цепочки в каждой группе можно получить друг из друга убрав бисерину с одной стороны и приставив к другой но в одной группе всего два варианта это произошло от того что сережки в этой группе состоят из двух повторяющихся сегментов то есть все варианты ограничиваются всего двумя поворотами поэтому в этой группе всего 2 элемента у элис не получится разделить сережки из четырех бисерин на равные группы а что будет с пятью бисеринами разделится ли такие сережки на одинаковые группы стоп alice внезапно поняла что ей необязательно даже проводить эксперимент сережки снова разделится поровну потому что 5 бисерин нельзя разделить на повторяющийся узор потому что 5 не делится на равные части это простое число поэтому какую последовательность разноцветная бисерин мы бы не взяли она всегда повторится ровно через пять поворотов или через пять переносов крайние бисерины в конец период повтора каждой цепочки бисерин равняется 5 давайте проверим сначала снова построим всевозможные последовательности из 5 бисерин удаляем 2 одноцветные цепочки неделям оставшиеся на группы в которых цепочки отличается лишь сдвигом и склеиваем из них сережки и каждой сережки для возврата в первоначальное состояние требуется ровно пять поворотов таким образом если из всех цепочек склеить сережки они разделятся на равные группы по 5 одинаковых серёжек тут элис делает еще один шаг до этого она брала бисерины двух цветов но теперь она поняла что закономерность должна соблюдаться для любого количества цветов потому что любая сережка из простого числа бисерин п будет превращение повторяться только через п поворотов простое число невозможно разделить на фрагменты равные длины но если взять составное число бисерин на пример 6 тогда всегда найдутся узоры которые будут повторяться через меньшее количество поворотов потому что они состоят из повторяющихся фрагментов значит они образуют меньшие группы то есть это то о чем говорится в малой теореме ферма если взять бисер от цветов и составить из бисерин цепочки длиной по где п простое число то количество возможных цепочек равно а умножить на а умножить на а п раз то есть а в степени p если убрать одноцветные цепочки то получится ровно а цепочек по одной цепочке каждого цвета то останется а в степени b минус a цепочек и если склеить из цепочек сережки тогда они разделятся на группы по п одинаковых серёжек в каждой потому что каждая сережка будет повторяться только через п поворотов таким образом а в степени b минус a делится на p вот и все можно записать то же самое через модульную арифметику если разделить а в степени b на b остаток от деления будет равняться а таким образом а в степени p равняется а по модулю п и мы получили один из фундаментальных законов теории чисел просто играя в бисер спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них