Наибольший общий делитель

В математике есть понятие «делимость». Оно означает, что одно число можно разделить на другое без остатка. Например, 12 делится на 3 без остатка:

12 : 3 = 4.

Если число делится само на себя и на единицу, то оно называется простым числом. Если же число имеет другие делители, кроме 1 и самого числа, то это составное число.

У каждого числа есть общие делители с другими числами. Но среди них есть наибольший общий делитель (НОД). Это наибольшее число, на которое оба числа делятся без остатка.

Чтобы найти НОД двух чисел, нужно выполнить следующие шаги:

• Разложить каждое число на простые множители.
• Выписать общие простые множители обоих чисел.
• Перемножить их. Полученное число и будет наибольшим общим делителем.

Рассмотрим пример нахождения НОД чисел 24 и 36.

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

24 = 2 2 2 3;36 = 2 2 3 3.

Общие простые множители этих чисел — 2 и 3. Их произведение равно 4. Значит, НОД (24; 36) = 4.

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

Например, найдём НОД чисел 84 и 21.

84 / 21 = 4 (остаток 0).

Теперь заменим 21 на остаток 0.

84 / 0 = (невозможно).

Значит, НОД (84; 21) = 21.

Вопросы:

1. Что такое делимость?
2. Какие числа называются простыми? Составными?
3. Что такое наибольший общий делитель?
4. Как найти наибольший общий делитель двух чисел?
5. В чём заключается алгоритм Евклида?

Примеры:

Найдите НОД следующих чисел:

а) 18 и 24; б) 72 и 96; в) 56 и 70.

Решение:

а) Разложим числа 18 и 24 на простые множители:

18 = 2 3 3,24 = 2 2 2 * 3.

Общими простыми множителями являются 2 и 3. Перемножим их: 2 * 3 = 6. Значит, НОД (18; 24) = 6.

б) Разложим числа 72 и 96 на простые множители:

72 = 2 2 2 3 3,96 = 2 2 2 2 2 * 3.

Общим простым множителем является 2 2 2 3. Его произведение равно 4 3 = 12. Значит, НОД (72; 96) = 12.

в) Разложим числа 56 и 70 на простые множители:

56 = 2 2 2 7,70 = 2 5 * 7.

Общий простой множитель — 7. Значит, НОД (56; 70) = 7.