Программа курса «Элементы теории чисел»

механико-математический факультет МГУ, 1 курс, 1 семестр

Делимость целых чисел. Наименьшее общее кратное и наибольший общий делитель. Алгоритм Евклида. Решение в целых числах линейных уравнений.

Простые и составные числа. Решето Эратосфена. Бесконечность множества простых чисел. Основная теорема арифметики. Разложение на простые сомножители наибольшего общего делителя и наименьшего общего кратного нескольких чисел, факториала. Теорема Чебышева о количестве простых чисел до заданной границы.

Арифметические функции. Мультипликативные функции и их свойства. Функция Мёбиуса и формула обращения. Функция Эйлера. Сумма делителей и число делителей натурального числа.

Числовые сравнения их основные свойства. Системы счисления, признаки делимости. Классы вычетов. Полная и приведенная системы вычетов. Теорема Вильсона. Теорема Эйлера и малая теорема Ферма. Приложения к криптографии: криптосистема RSA, ключевой обмен.

Сравнения с одним неизвестным. Сравнения первой степени. Китайская теорема об остатках. Полиномиальные сравнения по простому модулю. Полиномиальные сравнения по составному модулю и количество их решений.

Сравнения второй степени по простому модулю. Символ Лежандра и его свойства. Квадратичный закон взаимности. Символ Якоби и его свойства. Теорема о множестве простых чисел, для которых разрешимо данное квадратичное сравнение. Представление натуральных чисел в виде суммы двух и четырех квадратов. Рациональные точки на плоских кривых второго порядка. Представление нуля диагональными формами от трех переменных.

Показатель числа по заданному модулю. Существование первообразных корней по простому модулю. Первообразные корни по составным модулям. Индексы и их свойства. Двучленные сравнения.

Рациональные и иррациональные числа. Иррациональность корней и логарифмов. Нахождение рациональных корней многочленов с целыми коэффициентами. Иррациональность числа e. Представление рациональных чисел бесконечными десятичными дробями. Длина периода десятичной дроби.