#232. Малая теорема Ферма и псевдопростые числа

Малая теорема Ферма — красивейший факт из теории чисел, который через столетия после открытия сыграл важную роль в криптографии и защите информации!

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 встречается часто, так что полезно будет рассказать другой подход. Благо, мы уже обсуждали и простые числа в целом, и метод математической индукции, и бином Ньютона — ссылочки в конце описания. Мы также доберемся до теста Ферма и псевдопростых чисел. А если захотите продолжения — пишите в комментариях!

ОБЯЗАТЕЛЬНО ПОСМОТРИТЕ

#Математика #наука #научпоп

[WildMathing]

Ну что, дикие математики, когда Великую теорема Ферма будем доказывать?

[mathand]

Я придумал поистине смешной и интересный комментарий, но поля для ввода слишком малы для него.

[peskw]

БОЖЕ КАК Я РАД ЧТО НА РУССКОМ ЯЗЫКЕ ЕСТЬ ТАКИЕ КРУТЫЕ ВИДЕО ПРО МАТЕМАТИКУ, Я ТЕБЯ ЛЮБЛЮ, WILD MATHING

[tooman]

В уроке по криптографии разберём как работает шифрование биткоина посредством решения диофантового уравнения?

[kamranabdulkhaev]

0:43 Редкий случай когда Великая теорема Ферма записана со всеми условиями (левый нижний угол)

[fjxuvxm]

3 года назад: готовлюсь к ЕГЭ по видео WM
сейчас: готовлюсь к зачету по информационной безопасности по видео WM

[garvett]

2:18 Я, когда пытаюсь решить олимпиадную задачу по математике

[AlexeyEvpalov]

Интересное, познавательное видео. Спасибо за доказательство малой теоремы Ферма.

[MMJJKK]

0:21, похоже на принт для футболки...

[Dasistfantastisch]

Даю знать, что криптография - это очень интересно)

[akita]

Это видео под стать хэллоуину. В середине ролика успел испугаться, а под конец получил просветление, и понял, что бояться нечего. Спасибо за труд.

[andreym]

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

[ADMINADMIN-iwzy]

Даааа, а на первом курсе это казалось чем-то запутанным

[nickgonva]

Спасибо за видео, как раз недавно начал прорешивать задачи Эйлера на Python`e, но задачку с простыми числами всё не мог решить. Благодарю за объяснение!)

[frozenboy]

Кстати я помню того математика . Вообще он больше всего любил музыку, но как вышло так вышло . Не раз ко мне обращался, что бы я помог емк стать музыкантом .
До скорого 🤗💜

[denisshulakov]

Да это же проверка на простоту за асимптотику O(logN) причем честный логарифм - не больше 64 операций. И теперь я действительно осознал природу обратного по модулю - 1/a mod p = a^(p-2) mod p. Спасибо Wild Mathing!!!
PS ждём криптографию

[HoBrOpOgEc]

Учусь на втором курсе компьютерной безопасности, и если до этого я восторженно смотрел твои видео с мыслью «блин, это круто выглядит», то сейчас, могу спело заявить, как же круто смотреть видео, когда не по наслышке знаешь о чем оно и как это применить! Определенно лайк и больше видео о алгебраических моделях и их применениях :)

[catsandboots]

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

[drozdchannel]

расскажи про алгоритм шифрования RSA, там простые числа напрямую применяются

[kountrybolz]

Ничего не пойму, но знаю, что очень интересно слушать.