Делимость и остатки: основы теории чисел
Теория чисел — царица математики, и олимпиадные задачи не обходятся без неё. Понимание свойств делимости, НОД, НОК и признаков делимости необходимо для решения уравнений в целых числах.
Ключевым инструментом является арифметика остатков (сравнения по модулю). Запись a ≡ b (mod n) означает, что a и b дают одинаковый остаток при делении на n. Сравнения можно складывать, вычитать и умножать. Это позволяет легко находить последние цифры огромных степеней.
Важные теоремы: Малая теорема Ферма (если p — простое, то a^(p-1) ≡ 1 (mod p)) и Теорема Эйлера. Они помогают решать задачи на доказательство делимости сложных выражений. Также стоит изучить Основную теорему арифметики о единственности разложения на простые множители.
Диофантовы уравнения — это уравнения, которые нужно решить в целых числах. Простейшее линейное диофантово уравнение ax + by = c имеет решение тогда и только тогда, когда c делится на НОД(a, b). Для решения используется алгоритм Евклида.
