Наибольший общий делитель (НОД)

Наибольший общий делитель (НОД) двух или более чисел — это наибольшее число, которое делит каждое из данных чисел нацело.

Обозначение: $\text{НОД}(a,b)\backslash text\{НОД\}(a,\; b)$.

Свойства НОД

1. НОД всегда меньше или равен меньшему из чисел: Если $aa$ и $bb$ — два натуральных числа, то $\text{НОД}(a,b)\le \min (a,b)\backslash text\{НОД\}(a,\; b)\; \backslash leq\; \backslash min(a,\; b)$.

2. НОД делит оба числа: Если $d=\text{НОД}(a,b)d\; =\; \backslash text\{НОД\}(a,\; b)$, то $a\mathrm{m}\mathrm{o}\mathrm{d}d=0a\; \backslash mod\; d\; =\; 0$ и $b\mathrm{m}\mathrm{o}\mathrm{d}d=0b\; \backslash mod\; d\; =\; 0$.

3. Связь с НОК: НОД и НОК двух чисел связаны формулой:

   $\text{НОК}(a,b)\cdot \text{НОД}(a,b)=\mathrm{\mid }a\cdot b\mathrm{\mid }\mathrm{.}\backslash text\{НОК\}(a,\; b)\; \backslash cdot\; \backslash text\{НОД\}(a,\; b)\; =\; |a\; \backslash cdot\; b|.$

4. Если одно из чисел делит другое: Если $aa$ делится на $bb$, то $\text{НОД}(a,b)=b\backslash text\{НОД\}(a,\; b)\; =\; b$.

5. НОД нескольких чисел: Для трёх чисел $aa$, $bb$, $cc$:

   $\text{НОД}(a,b,c)=\text{НОД}(\text{НОД}(a,b),c)\mathrm{.}\backslash text\{НОД\}(a,\; b,\; c)\; =\; \backslash text\{НОД\}(\backslash text\{НОД\}(a,\; b),\; c).$

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

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

Шаги алгоритма:

1. Делим большее число на меньшее.
2. Остаток от деления заменяет большее число.
3. Повторяем деление до тех пор, пока остаток не станет равным 0. Последнее ненулевое число — это НОД.

Пример 1: Нахождение НОД для чисел 36 и 60

1. Делим $60÷36=160\; \backslash div\; 36\; =\; 1$ (остаток $2424$).
2. Делим $36÷24=136\; \backslash div\; 24\; =\; 1$ (остаток $1212$).
3. Делим $24÷12=224\; \backslash div\; 12\; =\; 2$ (остаток $00$).

Ответ: $\text{НОД}(36,60)=12\backslash text\{НОД\}(36,\; 60)\; =\; 12$.

Поиск НОД с использованием разложения на простые множители

1. Разложите оба числа на простые множители.
2. Найдите произведение общих множителей с их минимальными степенями.

Пример 2: Нахождение НОД через простые множители

Найдём $\text{НОД}(48,60)\backslash text\{НОД\}(48,\; 60)$.

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

   • $48=2^4\cdot 348\; =\; 2^4\; \backslash cdot\; 3$,
   • $60=2^2\cdot 3\cdot 560\; =\; 2^2\; \backslash cdot\; 3\; \backslash cdot\; 5$.

2. Найдём общие множители:

   • Общие множители: $22$ и $33$,
   • Общие степени: $2^{2}2^2$ и $3^{1}3^1$.

3. Перемножим:

   $\text{НОД}(48,60)=2^2\cdot 3=12.\backslash text\{НОД\}(48,\; 60)\; =\; 2^2\; \backslash cdot\; 3\; =\; 12.$

Ответ: $\text{НОД}(48,60)=12\backslash text\{НОД\}(48,\; 60)\; =\; 12$.

Применение НОД

1. Упрощение дробей: Для сокращения дроби $\frac{a}{b}\backslash frac\{a\}\{b\}$ нужно разделить числитель и знаменатель на их НОД.

2. Решение задач с делимостью: НОД используется для нахождения целых делителей чисел.

3. Распределение ресурсов: Задачи на равномерное деление предметов (например, порезать верёвку на равные части).

4. Связь с НОК: НОД помогает находить НОК чисел через формулу:

   $\text{НОК}(a,b)=\frac{\mathrm{\mid }a\cdot b\mathrm{\mid }}{\text{НОД}(a,b)}\mathrm{.}\backslash text\{НОК\}(a,\; b)\; =\; \backslash frac\{|a\; \backslash cdot\; b|\}\{\backslash text\{НОД\}(a,\; b)\}.$

Примеры

Пример 3: Упрощение дроби

Упростите дробь $\frac{36}{48}\backslash frac\{36\}\{48\}$.

1. Найдём $\text{НОД}(36,48)\backslash text\{НОД\}(36,\; 48)$:

   • $36=2^2\cdot 3^{2}36\; =\; 2^2\; \backslash cdot\; 3^2$,
   • $48=2^4\cdot 348\; =\; 2^4\; \backslash cdot\; 3$,
   • $\text{НОД}(36,48)=2^2\cdot 3=12\backslash text\{НОД\}(36,\; 48)\; =\; 2^2\; \backslash cdot\; 3\; =\; 12$.

2. Сократим дробь:

   $\frac{36}{48}=\frac{36÷12}{48÷12}=\frac{3}{4}\mathrm{.}\backslash frac\{36\}\{48\}\; =\; \backslash frac\{36\; \backslash div\; 12\}\{48\; \backslash div\; 12\}\; =\; \backslash frac\{3\}\{4\}.$

Ответ: $\frac{3}{4}\backslash frac\{3\}\{4\}$.

Пример 4: Решение уравнения

Найдите все натуральные $xx$, такие что $\text{НОД}(x,12)=4\backslash text\{НОД\}(x,\; 12)\; =\; 4$.

Решение:

1. $xx$ должно делиться на 4, так как $\text{НОД}(x,12)\backslash text\{НОД\}(x,\; 12)$ имеет общий делитель.
2. Общие делители $1212$ и $44$: $4,8,124,\; 8,\; 12$.

Ответ: $x=4,8x\; =\; 4,\; 8$.

Задачи для закрепления

1. Найдите $\text{НОД}(24,36)\backslash text\{НОД\}(24,\; 36)$ с использованием алгоритма Евклида.
2. Упростите дробь $\frac{72}{90}\backslash frac\{72\}\{90\}$.
3. Решите задачу: $\text{НОД}(x,18)=6\backslash text\{НОД\}(x,\; 18)\; =\; 6$. Найдите возможные значения $xx$.

Заключение

Наибольший общий делитель — это фундаментальное понятие в теории чисел, которое используется в задачах на делимость, упрощение дробей и распределение ресурсов. Метод Евклида и разложение на простые множители являются основными способами нахождения НОД. Формула связи НОД с НОК упрощает вычисления в задачах с кратными и делителями.