Делимость. НОД, НОК. Основная теорема арифметики

Содержание 15 разделов

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

1. Делимость чисел: базовые понятия

Делимость — это одно из фундаментальных понятий в математике. Говорят, что число $a$ делится на число $b$, если существует такое целое число $k$, что $a = b \cdot k$.

Обозначение: $a \mid b$ означает, что $a$ делит $b$ (или $b$ делится на $a$).

Свойства делимости

• Транзитивность: если $a \mid b$ и $b \mid c$, то $a \mid c$.
  Пример: $2 \mid 6$ и $6 \mid 18$ → $2 \mid 18$.
• Линейность: если $a \mid b$ и $a \mid c$, то $a \mid (b + c)$ и $a \mid (b - c)$.
  Пример: $3 \mid 6$ и $3 \mid 9$ → $3 \mid (6+9)=15$.
• Линейная комбинация: если $a \mid b$ и $a \mid c$, то $a \mid (b x + c y)$ для любых целых $x, y$.
  Пример: $3 \mid 6$ и $3 \mid 9$ → $3 \mid (6\cdot2 + 9\cdot5) = 57$.

2. Признаки делимости

Признаки делимости — это правила, которые позволяют быстро определить, делится ли число на заданное число, не выполняя деления.

Признаки для $4, 8, 25$ опираются на то, что $100$ делится на $4$ и на $25$, а $1000$ делится на $8$: старшие разряды заведомо кратны делителю, поэтому проверять достаточно «хвост» числа.

3. НОД и НОК

НОД — наибольший общий делитель

Определение: НОД двух чисел — это наибольшее натуральное число, на которое делятся оба числа.

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

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

Алгоритм Евклида для нахождения НОД

Алгоритм Евклида — это быстрый способ найти НОД двух чисел без разложения на множители.

Суть: делим большее число на меньшее, затем меньшее на остаток, и так до тех пор, пока остаток не станет равен нулю. Последний ненулевой остаток — это НОД.

4. Основная теорема арифметики (ОТА)

Основная теорема арифметики — это фундаментальное утверждение: любое натуральное число $n > 1$ можно единственным образом представить в виде произведения простых чисел (с точностью до порядка множителей).

где $p_1 < p_2 < \ldots < p_k$ — простые числа, $\alpha_i \ge 1$ — натуральные числа (показатели степеней).

Как найти НОД и НОК через разложение на простые множители

Правило:

• НОД — берём общие простые множители с наименьшими показателями.
• НОК — берём все простые множители с наибольшими показателями.

Свойство НОД и НОК

5. Количество делителей числа

Если число $n$ имеет каноническое разложение $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$, то количество его натуральных делителей вычисляется по формуле:

6. Взаимно простые числа

Два числа называются взаимно простыми, если у них нет общих делителей, кроме $1$.

7. Среднее арифметическое

Среднее арифметическое чисел $a_1, a_2, \ldots, a_n$ — это сумма чисел, делённая на их количество.

Важные свойства:

• Если добавить число меньше среднего, то среднее уменьшится.
• Если добавить число больше среднего, то среднее увеличится.

8. Простые и составные числа

• Простое число — имеет ровно два делителя: $1$ и само себя.
  Примеры: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.
• Составное число — имеет больше двух делителей.
  Примеры: $4, 6, 8, 9, 10, 12, \dots$
• Число 1 — не простое и не составное.
• Число 2 — единственное чётное простое число.

9. Тождество Безу

Тождество (соотношение) Безу утверждает, что НОД двух чисел можно представить в виде их линейной комбинации (не путайте с «теоремой Безу» об остатке от деления многочлена на $(x-a)$ — это другой, не связанный факт):

где $x, y$ — некоторые целые числа.