← Назад к темам

🔢 Теория чисел

Элементарная теория чисел и её приложения

📚 Основы теории чисел

Делимость и деление с остатком

Определение: Число $a$ делится на число $b$ (обозначается $b \mid a$), если существует целое число $k$ такое, что $a = bk$.

Теорема о делении с остатком: Для любых целых чисел $a$ и $b$ ($b > 0$) существуют единственные целые числа $q$ и $r$ такие, что:

$$a = bq + r, \quad 0 \leq r < b$$

где $q$ — частное, $r$ — остаток.

НОД и НОК

Наибольший общий делитель (НОД): $\gcd(a,b)$ — наибольшее положительное число, которое делит и $a$, и $b$.

Алгоритм Евклида:

$$\gcd(a,b) = \gcd(b, a \bmod b)$$

Наименьшее общее кратное (НОК):

$$\text{lcm}(a,b) = \frac{|a \cdot b|}{\gcd(a,b)}$$
Простые числа

Определение: Простое число — натуральное число больше 1, которое имеет ровно два делителя: 1 и само себя.

Основная теорема арифметики: Каждое натуральное число больше 1 можно единственным образом представить в виде произведения простых чисел.

Решето Эратосфена: Алгоритм для нахождения всех простых чисел до заданного $n$.

Сравнения по модулю

Определение: Числа $a$ и $b$ сравнимы по модулю $m$ (обозначается $a \equiv b \pmod{m}$), если $m \mid (a-b)$.

Свойства сравнений:

  • Рефлексивность: $a \equiv a \pmod{m}$
  • Симметричность: если $a \equiv b \pmod{m}$, то $b \equiv a \pmod{m}$
  • Транзитивность: если $a \equiv b \pmod{m}$ и $b \equiv c \pmod{m}$, то $a \equiv c \pmod{m}$
🟣 Легкий
Разложите число 420 на простые множители и найдите количество его делителей.
💡 Решение

Шаг 1: Разложим 420 на простые множители.

$420 = 2^2 \cdot 3 \cdot 5 \cdot 7$

Проверим пошагово:

  • $420 \div 2 = 210$
  • $210 \div 2 = 105$
  • $105 \div 3 = 35$
  • $35 \div 5 = 7$
  • $7$ — простое число

Шаг 2: Найдем количество делителей.

Формула: Если $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$, то количество делителей равно $(a_1+1)(a_2+1)\ldots(a_k+1)$.

Для $420 = 2^2 \cdot 3^1 \cdot 5^1 \cdot 7^1$:

Количество делителей = $(2+1)(1+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 \cdot 2 = 24$

Ответ: $420 = 2^2 \cdot 3 \cdot 5 \cdot 7$, количество делителей = 24

⚫ Средний
Найдите НОД(252, 198) и НОК(252, 198), используя алгоритм Евклида.
💡 Решение

Шаг 1: Найдем НОД(252, 198) с помощью алгоритма Евклида.

$\gcd(252, 198)$:

  • $252 = 198 \cdot 1 + 54$
  • $198 = 54 \cdot 3 + 36$
  • $54 = 36 \cdot 1 + 18$
  • $36 = 18 \cdot 2 + 0$

Поэтому $\gcd(252, 198) = 18$

Шаг 2: Найдем НОК, используя формулу.

$\text{lcm}(a,b) = \frac{a \cdot b}{\gcd(a,b)}$

$\text{lcm}(252, 198) = \frac{252 \cdot 198}{18} = \frac{49896}{18} = 2772$

Проверка:

  • $252 = 18 \cdot 14$
  • $198 = 18 \cdot 11$
  • $\text{lcm}(252, 198) = 18 \cdot 14 \cdot 11 = 18 \cdot 154 = 2772$ ✓

Ответ: НОД(252, 198) = 18, НОК(252, 198) = 2772

⚫ Средний
Решите сравнение: $3x \equiv 7 \pmod{11}$
💡 Решение

Нужно найти такое $x$, что $3x \equiv 7 \pmod{11}$.

Метод 1: Найдем обратный элемент к 3 по модулю 11.

Нужно найти $a$ такое, что $3a \equiv 1 \pmod{11}$.

Проверим: $3 \cdot 4 = 12 \equiv 1 \pmod{11}$

Значит, $3^{-1} \equiv 4 \pmod{11}$

Умножим обе части исходного сравнения на 4:

$4 \cdot 3x \equiv 4 \cdot 7 \pmod{11}$

$12x \equiv 28 \pmod{11}$

$x \equiv 6 \pmod{11}$

Метод 2: Расширенный алгоритм Евклида.

Найдем такие $x, y$, что $3x + 11y = \gcd(3,11) = 1$:

  • $11 = 3 \cdot 3 + 2$
  • $3 = 2 \cdot 1 + 1$
  • $2 = 1 \cdot 2 + 0$

Обратный ход:

  • $1 = 3 - 2 \cdot 1$
  • $1 = 3 - (11 - 3 \cdot 3) \cdot 1 = 3 \cdot 4 - 11 \cdot 1$

Поэтому $3 \cdot 4 \equiv 1 \pmod{11}$

Проверка: $3 \cdot 6 = 18 \equiv 7 \pmod{11}$ ✓

Ответ: $x \equiv 6 \pmod{11}$

🔴 Сложный
Найдите остаток от деления $2^{100}$ на 101, используя малую теорему Ферма.
💡 Решение

Шаг 1: Проверим, что 101 — простое число.

Нужно проверить делимость на простые числа до $\sqrt{101} \approx 10$:

  • 101 не делится на 2 (нечетное)
  • 101 не делится на 3 (сумма цифр = 2)
  • 101 не делится на 5 (не оканчивается на 0 или 5)
  • 101 не делится на 7: $101 = 7 \cdot 14 + 3$

Значит, 101 — простое число.

Шаг 2: Применим малую теорему Ферма.

Поскольку 101 — простое и $\gcd(2, 101) = 1$, то по малой теореме Ферма:

$2^{100} \equiv 1 \pmod{101}$

Объяснение: По малой теореме Ферма, если $p$ — простое число и $\gcd(a,p) = 1$, то $a^{p-1} \equiv 1 \pmod{p}$.

В нашем случае: $p = 101$, $a = 2$, $p-1 = 100$.

Ответ: $2^{100} \equiv 1 \pmod{101}$

Остаток от деления $2^{100}$ на 101 равен 1.

🔴 Сложный
Решите систему сравнений: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.
💡 Решение

Используем китайскую теорему об остатках.

Шаг 1: Проверим условия применимости.

Модули 3, 5, 7 попарно взаимно просты, поэтому система имеет единственное решение по модулю $3 \cdot 5 \cdot 7 = 105$.

Шаг 2: Найдем решение методом КТО.

Пусть $M = 3 \cdot 5 \cdot 7 = 105$

$M_1 = M/3 = 35$, $M_2 = M/5 = 21$, $M_3 = M/7 = 15$

Найдем обратные элементы:

  • $35 \equiv 2 \pmod{3}$, нужно $2y_1 \equiv 1 \pmod{3}$ → $y_1 = 2$
  • $21 \equiv 1 \pmod{5}$, нужно $y_2 \equiv 1 \pmod{5}$ → $y_2 = 1$
  • $15 \equiv 1 \pmod{7}$, нужно $y_3 \equiv 1 \pmod{7}$ → $y_3 = 1$

Шаг 3: Составим решение.

$x \equiv a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3 \pmod{M}$

$x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105}$

$x \equiv 140 + 63 + 30 \pmod{105}$

$x \equiv 233 \pmod{105}$

$x \equiv 23 \pmod{105}$

Проверка:

  • $23 = 3 \cdot 7 + 2$, поэтому $23 \equiv 2 \pmod{3}$ ✓
  • $23 = 5 \cdot 4 + 3$, поэтому $23 \equiv 3 \pmod{5}$ ✓
  • $23 = 7 \cdot 3 + 2$, поэтому $23 \equiv 2 \pmod{7}$ ✓

Ответ: $x \equiv 23 \pmod{105}$

🔴 Сложный
Найдите значение функции Эйлера $\phi(360)$ и вычислите $5^{\phi(360)} \bmod 360$.
💡 Решение

Шаг 1: Разложим 360 на простые множители.

$360 = 2^3 \cdot 3^2 \cdot 5^1$

Шаг 2: Вычислим $\phi(360)$.

Формула для функции Эйлера:

Если $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$, то:

$\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

$\phi(360) = 360 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{5}\right)$

$\phi(360) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 360 \cdot \frac{8}{30} = 360 \cdot \frac{4}{15} = 96$

Шаг 3: Вычислим $5^{96} \bmod 360$.

Поскольку $\gcd(5, 360) = 5 \neq 1$, теорему Эйлера напрямую применить нельзя.

Заметим, что $360 = 8 \cdot 9 \cdot 5$, где $\gcd(8,9) = \gcd(8,5) = \gcd(9,5) = 1$.

Найдем $5^{96}$ по модулям 8, 9, 5 отдельно:

  • $5^{96} \equiv 5^{96 \bmod 4} \equiv 5^0 \equiv 1 \pmod{8}$ (поскольку $\phi(8) = 4$)
  • $5^{96} \equiv 5^{96 \bmod 6} \equiv 5^0 \equiv 1 \pmod{9}$ (поскольку $\phi(9) = 6$)
  • $5^{96} \equiv 0 \pmod{5}$ (поскольку $5 \mid 5^{96}$)

Применим китайскую теорему об остатках к системе:

  • $x \equiv 1 \pmod{8}$
  • $x \equiv 1 \pmod{9}$
  • $x \equiv 0 \pmod{5}$

Из первых двух сравнений: $x \equiv 1 \pmod{72}$

Подставляя в третье: $x = 72k + 1 \equiv 0 \pmod{5}$

$72k + 1 \equiv 0 \pmod{5}$

$2k + 1 \equiv 0 \pmod{5}$

$2k \equiv 4 \pmod{5}$

$k \equiv 2 \pmod{5}$

Поэтому $x = 72 \cdot 2 + 1 = 145$

Ответ: $\phi(360) = 96$, $5^{96} \equiv 145 \pmod{360}$

🔬 Дополнительные темы

Функция Эйлера

Определение: $\phi(n)$ — количество натуральных чисел, не превосходящих $n$ и взаимно простых с $n$.

Свойства:

  • $\phi(p) = p-1$ для простого $p$
  • $\phi(p^k) = p^{k-1}(p-1)$ для простого $p$
  • $\phi(mn) = \phi(m)\phi(n)$ если $\gcd(m,n) = 1$
Теорема Эйлера

Если $\gcd(a,n) = 1$, то:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

Малая теорема Ферма является частным случаем теоремы Эйлера.

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

Если $m_1, m_2, \ldots, m_k$ попарно взаимно просты, то система сравнений:

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$$

имеет единственное решение по модулю $M = m_1m_2\ldots m_k$.

Практическое применение: Теория чисел лежит в основе современной криптографии, включая алгоритмы RSA, дискретное логарифмирование и эллиптические кривые.