Теория чисел для экзаменов и олимпиад

Некоторые известные формулы из теории чисел: основная теорема арифметики, расширенный признак делимости на 9, теорема Эйлера

О статье

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

Цель этой вводной статьи - обратить внимание всех заинтересованных - школьников и преподавателей, на данную тему.

На самом деле, зачастую и те и другие понимают, где и зачем нужна теория чисел. Например, понятно, что в ЕГЭ по математике в последнем задании могут понадобиться свойства целых чисел, которые и изучаются в теории чисел. Тем не менее, какие именно знания из этого обширного раздела могут оказаться полезны для каждого экзамена или олимпиад, для многих остается загадкой.

В школьной программе

Теорию чисел начинают изучать в школах довольно рано, уже в 5 классе школьникам рассказывают про делимость, учат признаки делимости, разложение на простые множители, НОД и НОК.

После 6 класса эта тема исчезает из программы обычных школ, оставляя от себя навык нахождения общего знаменателя при сложении дробей через НОК в лучшем случае.

Таким образом к старшим классам дети уже мало что помнят из этой темы.

На экзаменах

А в ЕГЭ попадаются задания, которые как утверждают составители не требуют дополнительных знаний кроме школьного курса. И как обычно и бывает, они правы. Только знания эти остались классе в 5-том и применялись к заданиям совсем другой сложности. И знания по теории чисел детям уже приходится освежать самостоятельно или с репетиторами.

Теория чисел нужна в математике и информатике, на экзаменах и олимпиадах. В информатике помимо математической теории, нужно еще понимать как переложить математические основы в эффективные алгоритмы и программный код.

ЕГЭ по математике

В ЕГЭ по математике теория чисел часто бывает необходима в последнем задании. Обычно здесь понадобятся минимальные знания из этого раздела:

1. Делимость. Свойства делимости.
2. Основная теорема арифметики - разложение на простые множители.
3. Расширенные признаки делимости на 3 и 9 - для остатков.
4. Арифметика остатков.
5. Формула количества делителей.

ЕГЭ по информатике

В ЕГЭ по информатике теория чисел нужна больше чем в математике. Дело в том, что информатика изначально ориентирована в большей степени не на непрерывные, а на дискретные данные, в частности на целые числа.

Минимальный список тем для ЕГЭ по информатике таким образом включает в себя список тем для ЕГЭ по математике. Также добавляются новые:

1. Системы счисления.
2. Алгоритм Евклида для нахождения НОД.
3. Алгоритм проверки числа на простоту. Решето Эратосфена.

В олимпиадах

В олимпиадах по математике и информатике теория чисел попадается во всех классах. Поэтому те, кто готовится к олимпиадам гораздо лучше готовы по этой теме к ЕГЭ.

Для решения олимпиадных задач больше важен опыт, навыки решения таких заданий и бывают необходимы дополнительные знания. Помимо тем, перечисленных для ЕГЭ, стоит обратить внимание как минимум на разделы:

1. Сравнения по модулю.
2. Диофантовы уравнения.
3. Теорема Эйлера. Малая Теорема Ферма.
4. Китайская теорема об остатках.

И как обычно, теория это только инструмент, с которым нужно научиться работать. Для этого нужно много практики.

© Сергей Бондаренко, 2023 г.

Теги: #математика #информатика #егэ #олимпиады #огэ