6. Малая теорема Ферма. Доказательство 1 и 2

• Школьная арифметика готовит к пониманию доказательств малой теоремы Ферма.  

• Малая теорема Ферма утверждает, что для любого простого числа p и любого числа a, a^p - a делится на p.  

• Пример: для p = 13, числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 дают остаток 1 при делении на 13.  

• Малая теорема Ферма формулируется в двух эквивалентных формах.  

• Первая форма: для любого простого p и любого целого a, a^p - a делится на p.  

• Вторая форма: для любого простого p и любого a, не делящегося на p, a^(p-1) - 1 делится на p.  

• Если a и a^(p-1) дают одинаковые остатки при делении на p, то их разность также дает остаток 1.  

• Доказательство включает рассмотрение остатков и их арифметических действий.  

• Малая теорема Ферма лежит в основе современных систем шифрования и кодирования.  

• Рассматривается арифметика остатков при делении на p.  

• Утверждается, что если два числа отличаются кратным p, то их степени также отличаются кратным p.  

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

• Малая теорема Ферма лежит в основе современных систем шифрования, таких как биткоин.  

• Понимание этой теоремы необходимо для понимания современных криптографических алгоритмов.  

• Второе доказательство использует графы и является более инструктивным.  

• Пример: графы по модулю 7 и 13.  

• Обсуждение мода восемь и его поведения.  

• Пример с подопытным кроликом двойкой.  

• Переход к модулю девять и подопытному кролику тройке.  

• Перемещение элементов и создание циклов.  

• Пример с модом девять и подопытным кроликом тройкой.  

• Обнаружение пересекающихся циклов разной длины.  

• Пример с тройкой и модом семь.  

• Появление циклов разной длины и их пересечение.  

• Решение не заниматься непростыми числами.  

• Утверждение о циклах в графике умножения на число а.  

• Доказательство, что разные остатки переходят в разные числа.  

• Взаимнооднозначное соответствие и циклы одинаковой длины.  

• Понятие порядка остатка и его важность.  

• Доказательство, что а в степени рр равно единице.  

• Определение порядка остатка и его влияние на циклы.  

• Вопрос о существовании остатка, порождающего один цикл.  

• Пример с двойкой и тройкой.  

• Утверждение, что для любого простого числа существует остаток, порождающий все остальные не нулевые остатки.  

• Понятие первообразных корней.  

• Пример с модом семь и первообразными корнями.  

• Важность существования первообразных корней для группы.  

• Группа остатков от деления на простое число по умножению всегда циклическая.  

• Для простого числа 2017 все ненулевые остатки вытягиваются в одну линию степеней одного из них.  

• Число 10 в степени от 1 до 2015 полностью покрывает все различные остатки от деления на 2017.  

• Это экспериментальный факт, подтвержденный на компьютере или через исследования.  

• Утверждение о существовании первообразных корней будет рассмотрено позже.  

• В следующем ролике будет исследоваться многочлены с остатками.  

• Малая тернарная ферма поможет в нетривиальных утверждениях.  

• После изучения многочленов будет установлено, что первообразные корни всегда существуют.