План подготовки к олимпиадам по математике в Казахстане (Теория чисел)

Содержание

• Лицензия
• Авторы Плана
• Введение
• База
• Китайская теорема об остатках
• Степени в теории чисел
• Первообразные корни
• $p$-adic evaluation
• Квадратичный закон взаимности
• Циклотомические многочлены
• Арифметические функции
• Разное
• Дополнительные источники

Лицензия

Настоящий план подготовки является предметом интеллектуальной собственности ОФ Beyond Curriculum и лицензирован под условиями CC BY-NC-ND 4.0 . Вы можете распространять этот план подготовки частично или целиком при следующих условиях: вы обязаны указать правообладателя (BY, ОФ "Beyond Curriculum") с активной ссылкой на первоисточник, при этом, вы не можете видоизменять план подготовки (ND) и вы должны использовать его исключительно в некоммерческих целях (NC).

Напоминаем, что Республика Казахстан (как и многие другие страны) присоединилась к Бернской конвенции Законом РК № 297-1 от 10.11.1998 г., и конвенция вступила в законную силу с 12 апреля 1999 года. Согласно данной конвенции, страны участницы уважают авторское право других стран участниц в той же мере, в которой они уважают авторские права своих граждан.

Авторы Плана

Идеи и материалы этого плана были предоставлены Мырзатай Айбеком и отредактированы Арсланом Даминовым. Айбек — золотой медалист IMO, абсолютный чемпион и золотой медалист республиканских олимпиад, абсолютный чемпион и золотой медалист IZhO. Арслан — серебряный медалист IZhO, АПМО, МОШП и республиканских олимпиад.

IZhO — Международная Жаутыковская олимпиада, IMO — Международная Математическая олимпиада (самая престижная в мире), BMO — Балканская Математическая олимпиада, АПМО — Азиатская Тихоокеанская Математическая олимпиада, МОШП — Международная Олимпиада Шелковый Путь.

Введение

Данная программа поделена на четыре раздела. Для достижения наилучшей эффективности рекомендуется заниматься ими равномерно.

Для закрепления тем, мы предлагаем вам решать задачи по тегам в Орбитали. Но подборки, по большей части, создают искусственную обстановку. На олимпиаде не будет написано тем перед задачами, поэтому не стоит забывать о практике.

Стоит сказать, что не существует конкретного плана подготовки, изучив которые вы станете успешно выступать на олимпиадах. Одна из причин — это то, что разным людям нужно разное кол-во времени для усвоения материала: одним достаточно 10 задач, чтобы понять общую суть метода, когда как другим на это понадобится 20-30 задач. Наша логика была в том, что лучше дать больше материалов для закрепления, чем меньше, поэтому если у вас возникает чувство, что задачи лёгкие — пропускайте их. И помните, что цель состоит не в изучении максимального количества книг или статей, а в получении максимального объёма математических навыков и знаний, а уж как вы будете их добывать — решать вам, мы лишь даём рекомендации.

База

1. Глава 3: Алгоритм Евклида и основная теорема Арифметики — Алгебра и Теория для Математических Школ от Н.Б. Алфутова, А. В Устинова (без чисел Люка и Цепных дробей)

2. Глава 4: Арифметика Остатков — Алгебра и Теория для Математических Школ от Н.Б. Алфутова, А. В Устинова

3. Chapter 1: Divisibility — Olympiad Number Theory Through Challenging Problems by Justin Stevens

4. Chapter 2: Divisibility — Number Theory: Structures, Examples, and Problems by Titu Andreescu

5. Chapter 2: Modular Arithmetic — Olympiad Number Theory Through Challenging Problems by Justin Stevens

6. Chapter 2: Powers of Integers — Number Theory: Structures, Examples, and Problems by Titu Andreescu

7. Chapter 3: Floor Function and Fractional Steps — Number Theory: Structures, Examples, and Problems by Titu Andreescu

8. Chapter 4: Digits of Numbers — Number Theory: Structures, Examples, and Problems by Titu Andreescu

   Примечание: эта статья также может быть дополнена Chapter 16: Sum of Digits — Problems from the Book by Titu Andreescu.

9. Chapter 5: Basic Principles in Number Theory — Number Theory: Structures, Examples, and Problems by Titu Andreescu

10. Chapter 3: $p$-adic Valuation — Olympiad Number Theory Through Challenging Problems by Justin Stevens

11. Chapter 7: More on Divisibility — Number Theory: Structures, Examples, and Problems by Titu Andreescu

12. Lifting the Exponent Lemma by Amir Hossein Parvardi. Решения: solutions.

13. Chapter 5: Problem Solving Strategies — Olympiad Number Theory Through Challenging Problems by Justin Stevens

Китайская теорема об остатках

1. The Chinese Remainder Theorem by Evan Chen
2. Chapter 7.1: Chinese Remainder Theorem — Number Theory: Structures, Examples, and Problems by Titu Andreescu

Степени в теории чисел

Под эту категорию я вставил все, что связано $a^n, a^n-b^n, a^n+b^n$ под определёнными модулями. Сюда входят теорема Эйлера, показатели, первообразные корни и так далее. Это почти что базовый инструмент в теории чисел. Им очень легко овладеть, достаточно решить достаточное количество задач на эту тему, чтобы понять природу поведения экспонент в теории чисел.

1. A Note on the Carmichael Function by Yimin Ge
2. Exponents and Primes by Alexander Remorov

Подсказки: hints

Примечание: главное для вас это решить последние 12 задач. 3. Remainder of $Aa^x+B^x$ by Yimin Ge

Первообразные корни

1. Chapter 7.3.3: Primitive Roots modulo (n) — Number Theory: Concepts and Problems by Titu Andreescu
2. 3 Problems on Primitive Roots

$p$-adic evaluation

1. Chapter 6.1: The yoga of $p$-adic valuations — Number Theory: Concepts and Problems by Titu Andreescu
2. Chapter 6.2: Legendre's Formula — Number Theory: Concepts and Problems by Titu Andreescu

Квадратичный закон взаимности

Это тоже одна из технических вещей, которые надо знать, если задача на такую тему придет на олимпиаде (например Республиканская олимпиада за 2019 год, шестая задача, 10 класс).

1. Chapter 9.1: Quadratic Residues; the Legendre Symbol — Number Theory: Structures, Examples, and Problems by Titu Andreescu
2. Chapter 18: Quadratic Residue — Problems from the Book by Titu Andreescu
3. Chapter 5.4: Quadratic residues and quadratic reciprocity — Number Theory: Concepts and Problems by Titu Andreescu

Циклотомические многочлены

1. Cyclotomic Polynomials In Number Theory by Lawrence Sun
2. Elementary Properties of Cyclotomic Polynomials by Yimin Ge

Арифметические функции

Скорее всего, задачи на эту тему не придут на олимпиадах. Но если вам будет интересно как ведут себя мультипликативные функции в задачах олимпиадного характера, то можете посмотреть вот это:

1. Chapter 6.1: Multiplicative functions — Number Theory: Structures, Examples, and Problems by Titu Andreescu

   Примечание: теорию рекомендуем посмотреть.

2. Chapter 4.4: Arithmetic functions — Number Theory: Concepts and Problems by Titu Andreescu

   Примечание: опционально, однако посмотреть задачи однозначно стоит.

Разное

1. A Nice Lemma in Congruence (Thue’s Lemma) by Masum Billal
2. Residue Classes with order 1 or 2 and a Generalization of Wilson’s Theorem by Yimin Ge
3. Polynomial Division in Number Theory by James Rickards
4. Chapter 5: Congruences involving prime numbers — Number Theory: Concepts and Problems by Titu Andreescu
5. Chapter 17: At the Border of Analysis and Number Theory — Problems from the Book by Titu Andreescu

Дополнительные источники

Если у вас есть привычка на досуге читать математические статьи (не решая), тогда вы можете почитать эти. Также вы их можете порешать, они абсолютно факультативны.

1. Set of Articles by PEN 2008
2. Set of Articles by PEN 2009
3. Number Theory: Concepts and Problems by Titu Andreescu
4. Chapter 3, 4 — Problems from the Book by Titu Andreescu