Малая теорема Ферма — красивейший факт из теории чисел, который через столетия после открытия сыграл важную роль в криптографии и защите информации!
Задачник: [ Ссылка ]
Мои курсы: [ Ссылка ]
Донат: [ Ссылка ]
VK: [ Ссылка ]
0:00 — История возникновения
0:25 — Формулировка
0:57 — Доказательство. База индукции
1:17 — Доказательство. Шаг индукции
3:50 — Вопрос: как обобщить до любых целых оснований?
4:12 — Тест Ферма: простое или составное?
5:17 — Другая формулировка МФТ
6:03 — УДИВИТЕЛЬНЫЙ ФАКТ!
Формулировка 1. Если p — простое число, a — целое число, то a^p≡a (mod p).
Формулировка 2. Если p — простое число, a — целое число, которое не делится на p, то a^(p-1) ≡1 (mod p).
Элементарное доказательство на YouTube встречается часто, так что полезно будет рассказать другой подход. Благо, мы уже обсуждали и простые числа в целом, и метод математической индукции, и бином Ньютона — ссылочки в конце описания. Мы также доберемся до теста Ферма и псевдопростых чисел. А если захотите продолжения — пишите в комментариях!
ОБЯЗАТЕЛЬНО ПОСМОТРИТЕ
1. Бином Ньютона: [ Ссылка ]
2. Простые числа и гипотеза Римана: [ Ссылка ]
3. Метод математической индукции I: [ Ссылка ]
4. Метод математической индукции II: [ Ссылка ]
#Математика #наука #научпоп
#232. Малая теорема Ферма и псевдопростые числа
Теги
математиканауканаучпопwild mathingкриптографияшифрenigmaтеория чиселтеорема Фермаголоволомкабином Ньютонадоказательствовысшая математикаАртур ШарифовАлексей Савватееварифметика11 классолимпиадаЕГЭвузпоступлениемехматВМКматфакВШЭМФТИобразованиеСириустест Фермамалая теорема Фермапсевдопростые числапростые числагипотеза Риманапроблема тысячелетияшифрование данных
