Элементы теории чисел

Автор программы курса: Герман Олег Николаевич

Аннотация

Курс посвящен изучению основ теории чисел. А именно, изучаются свойства делимости, линейные диофантовы уравнения, мультипликативные функции, линейные и полиномиальные сравнения по модулю, цепные дроби.

Необходимые базовые знания для прохождения курса. 

Дстаточно владеть школьной программой по математике.

План курса

Лекция 1. Делимость. Элементарные свойства делимости. Деление с остатком. Наибольший общий делитель и наименьшее общее кратное. Важная лемма. Алгоритм Евклида. Теорема Ламе.

Лекция 2. Конечные цепные дроби. Рекуррентные соотношения для числителей и знаменателей подходящих дробей. Представление н.о.д. двух чисел в виде их линейной комбинации.

Лекция 3. Линейные диофантовы уравнения. Матричный алгоритм. Основная теорема арифметики.

Лекция 4. Мультипликативные функции. Формула обращения Мебиуса. Мультипликативность функции Эйлера.

Лекция 5. Сравнения по модулю. Элементарные свойства сравнений. Классы вычетов. Сложение и умножение классов вычетов. Полная и приведенная системы вычетов. Теорема Эйлера, Малая теорема Ферма, теорема Вильсона. Показатель вычета по модулю. Алгоритм шифрования RSA.

Лекция 6. Китайская теорема об остатках. Мультипликативность количества решений полиномиального сравнения. Количество решений полиномиального сравнения по простому модулю.

Лекция 7. Подъем решения полиномиального сравнения. Лемма Гензеля.

Лекция 8. Сравнения второй степени. Квадратичные вычеты. Критерий Эйлера.

Лекция 9. Символ Лежандра. Элементарные свойства символа Лежандра. Лемма Гаусса.

Лекция 10. Квадратичный закон взаимности.

Лекция 11. Символ Якоби и его свойства.

Лекция 12. Первообразные корни. Существование первообразных корней по простому модулю. Построение общего ключа для шифрования.

Лекция 13. Бесконечные цепные дроби. Теорема Эйлера--Лагранжа.

Литература

1. Нестеренко Ю.В. «Теория чисел».

Дополнительная информация