Лекция 2. Модульная арифметика

0:00:00 Заставка 0:00:11 Вступление 0:03:48 Содержание лекции 0:04:00 Сравнения и действия над ними 0:13:28 Вычеты и классы вычетов 0:19:50 Кольцо вычетов 0:21:25 Обратные вычеты и поле вычетов 0:30:08 Признаки делимости 0:32:02 Решение сравнений 0:35:02 Решение системы сравнений с помощью КТО 0:38:56 Примеры использования КТО 0:50:28 Применение модульной арифметики 0:53:50 Малая теорема Ферма 1:06:45 Теорема Вильсона 1:16:20 Функция Эйлера и ее свойства 1:19:30 Вывод формулы для вычисления функции Эйлера 1:33:05 Примеры вычисления функции Эйлера 1:38:55 Теорема Эйлера 1:42:16 Вычисление обратных вычетов с помощью функции Эйлера 1:55:20 Вычисление обратных вычетов с помощью расширенного алгоритма Эвклида 2:01:17 Вычисление обратных вычетов методом цепных дробей 2:03:55 Эффективность вычислительных алгоритмов 2:06:15 Примеры полиномиальных и неполиномиальных алгоритмов 2:10:10 Алгоритмы проверки числа на простоту 2:15:36 Использованная литература