Теория чисел

О курсе

Делимость и алгоритм Евклида, соотношение Безу и диофантовы уравнения, разложение на простые и функции делителей. Сравнения, обратный по модулю, быстрое возведение в степень, китайская теорема об остатках. Теоремы Ферма, Эйлера и Вильсона, тест Ферма и числа Кармайкла. Простые: решето, распределение x / ln x, формула Лежандра. Порядки и первообразные корни, квадратичные вычеты и закон взаимности, цепные дроби, уравнение Пелля и RSA. Продолжение блока теории чисел из дискретной математики.

Программа курса: 32 урока

Делимость и алгоритм Евклида

  1. Делимость и деление с остатком
  2. НОД и алгоритм Евклида
  3. Соотношение Безу
  4. Линейные диофантовы уравнения
  5. Разложение на простые и делители
  6. Контроль: делимость и Евклид

Сравнения и китайская теорема

  1. Сравнения по модулю
  2. Обратный по модулю и сравнение ax ≡ b
  3. Быстрое возведение в степень
  4. Китайская теорема об остатках
  5. Системы с не взаимно простыми модулями
  6. Контроль: сравнения и китайская теорема

Теоремы Ферма, Эйлера и Вильсона

  1. Малая теорема Ферма
  2. Функция Эйлера
  3. Теорема Эйлера
  4. Теорема Вильсона
  5. Тест Ферма и числа Кармайкла
  6. Контроль: теоремы Ферма, Эйлера, Вильсона

Простые числа

  1. Решето Эратосфена и бесконечность простых
  2. Распределение простых
  3. Простые в факториале: формула Лежандра
  4. Контроль: простые числа

Порядки, первообразные корни, квадратичные вычеты

  1. Порядок элемента
  2. Первообразные корни и дискретный логарифм
  3. Квадратичные вычеты и символ Лежандра
  4. Квадратичный закон взаимности
  5. Контроль: порядки и вычеты

Цепные дроби, уравнение Пелля, RSA

  1. Цепные дроби
  2. Уравнение Пелля
  3. RSA
  4. Контроль: цепные дроби, Пелль, RSA

Итоговый тест

  1. Итоговый тест по теории чисел