О курсе
Делимость и алгоритм Евклида, соотношение Безу и диофантовы уравнения, разложение на простые и функции делителей. Сравнения, обратный по модулю, быстрое возведение в степень, китайская теорема об остатках. Теоремы Ферма, Эйлера и Вильсона, тест Ферма и числа Кармайкла. Простые: решето, распределение x / ln x, формула Лежандра. Порядки и первообразные корни, квадратичные вычеты и закон взаимности, цепные дроби, уравнение Пелля и RSA. Продолжение блока теории чисел из дискретной математики.
Программа курса: 32 урока
Делимость и алгоритм Евклида
- Делимость и деление с остатком
- НОД и алгоритм Евклида
- Соотношение Безу
- Линейные диофантовы уравнения
- Разложение на простые и делители
- Контроль: делимость и Евклид
Сравнения и китайская теорема
- Сравнения по модулю
- Обратный по модулю и сравнение ax ≡ b
- Быстрое возведение в степень
- Китайская теорема об остатках
- Системы с не взаимно простыми модулями
- Контроль: сравнения и китайская теорема
Теоремы Ферма, Эйлера и Вильсона
- Малая теорема Ферма
- Функция Эйлера
- Теорема Эйлера
- Теорема Вильсона
- Тест Ферма и числа Кармайкла
- Контроль: теоремы Ферма, Эйлера, Вильсона
Простые числа
- Решето Эратосфена и бесконечность простых
- Распределение простых
- Простые в факториале: формула Лежандра
- Контроль: простые числа
Порядки, первообразные корни, квадратичные вычеты
- Порядок элемента
- Первообразные корни и дискретный логарифм
- Квадратичные вычеты и символ Лежандра
- Квадратичный закон взаимности
- Контроль: порядки и вычеты
Цепные дроби, уравнение Пелля, RSA
- Цепные дроби
- Уравнение Пелля
- RSA
- Контроль: цепные дроби, Пелль, RSA
Итоговый тест
- Итоговый тест по теории чисел