1. Алгоритм Евклида и линейное представление наибольшего общего делителя. Линейные диофантовы уравнения с двумя неизвестными.
2. Сравнения. Определение, связь с остатками, свойства эквивалентности, арифметические свойства сравнений.
3. Разложение натурального числа в позиционной системе счисления с основанием
. Определение, доказательство существования и единственности разложения.
4. Система счисления со смешанными основаниями. Теорема о существовании и единственности разложения. Факториальная система счисления.
5. Полная и приведенная системы вычетов и их свойства.
6. Понятие обратного вычета. Существование и единственность: нужно указать (с доказательством, разумеется) необходимое и достаточное
условие существование обратного вычета и доказать его единственность. Быстрый алгоритм нахождения обратного вычета.
7. Малая теорема Ферма и теорема Эйлера.
8. Теорема Вильсона.
9. Сравнения первой степени с одним неизвестным.
10. Китайская теорема об остатках.
11. Алгоритмы решения системы сравнений из Китайской теоремы об остатках. (Алгоритмов было два — вспомните, пожалуйста, оба.)
12. Определение и простейшие свойства мультипликативных функций.
13. Функции
и
. Доказательство мультипликативности и формулы для этих функций.
14. Функция
. Доказательство ее мультипликативности. Формула для
.
15. Сумма значений мультипликативной функции по всем делителям числа. Сумма значений функции Эйлера по всем делителям числа.
16. Арифметические и геометрические прогрессии. Формулы суммы первых n членов.
17. Неравенство Бернулли.
18. Среднее арифметическое, геометрическое, гармоническое и квадратичное. Неравенства между этими средними для двух чисел.
19. Степень вхождения простого числа
в разложение
.
20. Тождество Эйлера (про сумму квадратов).
