Урок 6 Получить доступ за 75 баллов Наибольший общий делитель. Взаимно простые числа

Сейчас мы научимся определять наибольший общий делитель для двух или трех чисел, познакомимся с алгоритмом Евклида и узнаем много всего интересного.

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

При поиске НОД, например, 36 и 24, надо:

1. Записать их в виде разложения на простые множители

$$\mathbf{36 = 2\cdot2\cdot3\cdot3}$$

$$\mathbf{24 = 2\cdot2\cdot2\cdot3}$$

2. Среди множителей \(\mathbf{2\cdot2\cdot3\cdot3}\) и \(\mathbf{2\cdot2\cdot2\cdot3}\), которые входят в разложения этих чисел, нужно оставить только одинаковые множители - это \(\mathbf{2\cdot2\cdot3}\)

3. Вычислить произведение множителей, которые остались: \(\mathbf{2\cdot2\cdot3 = 12}\)

В итоге НОД чисел 36 и 24 равен 12.

Если при нахождении НОДа среди чисел есть одно, на которое делятся все остальные, то оно и будет тем самым НОДом.

Например, у чисел 12, 36 и 48 НОД = 12

Пример 1

Найдите все общие делители чисел:

А) 70, 105

Б) 18, 24

В) 45,75

Г) 324, 111, 432

Д) 320, 640, 960

Решение

А)

$$\mathbf{70  = 2\cdot5\cdot7}$$

$$\mathbf{105 = 3\cdot5\cdot7}$$

$$\mathbf{НОД (70; 105) = 5\cdot7 = 35}$$

Б)

$$\mathbf{18 = 2\cdot3\cdot3}$$

$$\mathbf{24 = 2\cdot2\cdot2\cdot3}$$

$$\mathbf{НОД (18; 24) = 2\cdot3 = 6}$$

В)

$$\mathbf{45 = 3\cdot3\cdot5}$$

$$\mathbf{75 = 3\cdot5\cdot5}$$

$$\mathbf{НОД (45; 75) = 3\cdot5 = 15}$$

Г)

$$\mathbf{324 = 2\cdot2\cdot3\cdot3\cdot3\cdot3}$$

$$\mathbf{111 = 3\cdot37}$$

$$\mathbf{432 = 2\cdot2\cdot2\cdot2\cdot3\cdot3\cdot3}$$

$$\mathbf{НОД (324; 111; 432) = 3}$$

Д)

$$\mathbf{320 = 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot5}$$

$$\mathbf{640 = 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot5}$$

$$\mathbf{960 = 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot3\cdot5}$$

$$\mathbf{НОД (320; 640; 960) = 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot5 = 320}$$

Пример 2

На новогоднем утреннике дети получили пакеты с подарками. Всего во всех пакетах находилось 159 апельсинов и 106 яблок. Сколько детей было на новогодней ёлке? Сколько в каждом пакете было яблок и сколько апельсинов?

Решение

$$\mathbf{159 = 3\cdot53}$$

$$\mathbf{106 = 2\cdot53}$$

$$\mathbf{НОД (159; 106) = 53}$$

Ребят на елке было 53 человека. В каждом пакете подарка было по 3 апельсина и 2 яблока.

Пример 3

Для выезда на природу работникам предоставили несколько автобусов. В каждом автобусе равное число мест для сидения. 184 человека выехали в лес, а 138 отправились на озеро. Так вышло, что все места в автобусах были заняты, и, стоя, никто не ехал. Сколько автобусов было и сколько пассажиров ехало в каждом из них?

Решение

$$\mathbf{184 = 2\cdot2\cdot2\cdot23}$$

$$\mathbf{138 = 2\cdot3\cdot23}$$

$$\mathbf{НОД (184; 138) = 46}$$

В каждом автобусе было по 46 мест. В лес поехало 4 автобусов, а на озеро поехало 3 автобусов. Всего было 4 + 3 = 7 автобусов.

Давайте разберёмся с некоторыми натуральными числами.

Число 15 имеет делители 1, 3, 5, а число 16 имеет делители 1, 2, 4, 8

У этих чисел единственный одинаковый делитель - это число 1 , поэтому они будут называться взаимно простыми.

Рассмотрев этот и другие примеры, не сложно догадаться, что натуральные числа, у которых НОД равен 1, называются взаимно простые.

Пример 1

Возьмем две пары чисел 12 и 18, 13 и 21. Выясним, есть ли среди них взаимно простые числа. Для этого каждое из чисел распишем по простым делителям.

12 имеет делители 1, 2, 3, 4, 6, 12

18 имеет делители 1, 2, 3, 6, 9, 18

Значит, числа 12 и 18 кроме единицы имеют общие делители 2, 3, 6, поэтому они не являются взаимно простыми числами. Повторим действия с другой парой чисел 13 и 21.

Число 13 делится нацело на 1, 13, а число 21 делится нацело на 1, 3, 7, 21.

Тут уже ситуация другая. 13 и 21 имеют единственный общий делитель - 1.

Значит, вторая пара чисел состоит из взаимно простых.

Пример 2 

Пусть у нас есть два числа 45 и 32, которые являются натуральными и составными.

Первое из них 45 имеет делители 1, 3, 5, 9, 15, 45, а натуральное число 32 имеет делители 1, 2, 4, 8, 16, 32

Оба числа из этой пары имеют единственный общий делитель- 1

Значит, числа 45 и 32 являются взаимно простыми. Запишем оба числа в виде разложения на простые множители

$$\mathbf{45 = 3\cdot3\cdot5}$$

$$\mathbf{32 = 2\cdot2\cdot2\cdot2\cdot2}$$

Числа из нашего примера, 45 и 32, в записи на множители не содержат равных чисел. Значит, разложения на простые множители двух и более взаимно простых чисел не включают одинаковых простых множителей.

Пример 3

Являются ли взаимно простыми числа:

А) 55 и 40

Б) 77 и 92

В) 14, 32 и 41

Г) 231 и 298

Д) 68 и 137

Решение:

А)

$$\mathbf{55 = 5\cdot11}$$

$$\mathbf{40 = 2\cdot2\cdot2\cdot5}$$

$$\mathbf{НОД (55; 40)  = 5}$$

Нет, не являются взаимно простыми числами

Б)

$$\mathbf{77 = 7\cdot11}$$

$$\mathbf{92 = 2\cdot2\cdot23}$$

$$\mathbf{НОД (77; 92) = 1}$$

Да, являются взаимно простыми числами

В)

$$\mathbf{14 = 2\cdot7}$$

$$\mathbf{32 = 2\cdot2\cdot2\cdot2\cdot2}$$

$$\mathbf{41 - простое\:число}$$

$$\mathbf{НОД (14; 32; 41) = 1}$$

Да, являются взаимно простыми числами

Г)

$$\mathbf{231 = 3\cdot7\cdot11}$$

$$\mathbf{298 = 2\cdot149}$$

$$\mathbf{НОД (231; 298) = 1}$$

Да, являются взаимно простыми числами

Д)

$$\mathbf{68 = 2\cdot2\cdot17}$$

$$\mathbf{137- простое}$$

$$\mathbf{НОД (68; 137) = 1}$$

Да, являются взаимно простыми числами

Пример 4

Найдите разложение на простые множители наибольшего общего делителя чисел a и b, если:

А) \(\mathbf{a = 2\cdot3\cdot5\cdot2\cdot3}\) и  \(\mathbf{b = 2\cdot2\cdot5\cdot7}\)

Б) \(\mathbf{a = 3\cdot5\cdot5\cdot7\cdot17}\) и \(\mathbf{b = 5\cdot3\cdot3\cdot17}\)

Решение

А) \(\mathbf{НОД (a; b) = НОД (2\cdot3\cdot5\cdot2\cdot3; 2\cdot2\cdot5\cdot7) = 2\cdot2\cdot5 = 20}\)

Б) \(\mathbf{НОД (a; b) = НОД (3\cdot5\cdot5\cdot7\cdot17; 5\cdot3\cdot3\cdot17) = 5\cdot3\cdot17 = 255}\)

Признак делимости на произведение взаимно простых чисел: если данное натуральное число делится на каждое из взаимно простых чисел, то оно делится и на их произведение.

Рассмотрим этот признак на примере трех взаимно простых чисел.

Возьмем, например, 420.

Число 420 без остатка делится на 2, на 5 и на 7.

Числа 2, 5, 7 являются взаимно простыми (так как их НОД равен 1). Проверим, будет ли делиться 420 на произведение взаимно простых чисел 2, 5 и 7.

\(\mathbf{2\cdot5\cdot7 = 70}\)

\(\mathbf{\frac{420}{70} = 6}\)

Очевидно, что 420 делится нацело на произведение чисел двух, пяти и семи.

Правило можно применять для любого количества множителей.

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

$$\frac{105}{38} = 2+\frac{1}{1+\frac{1}{3+\frac{1}{4+\frac{1}{2}}}}$$

Кроме того, алгоритм используется при решении линейных диофантовых уравнений. Это такие уравнения, у которых могут быть несколько неизвестных целых величин, и все их нужно найти. Например, может быть такое уравнение:

$$\mathbf{2x+3y = 1}$$

Решением этого уравнения будет пара чисел

$$\mathbf{x = 5}$$ и $$\mathbf{y = -3}$$

Могут быть и другие пары решений. Решение таких уравнений начинается обычно с нахождения НОДа чисел, стоящих перед неизвестными. В нашем случае мы бы находили \(\mathbf{НОД(2, 3)}\)

Не всегда данный алгоритм позволяет быстро решать задачи. Иногда можно потратить много времени, сделать много вычислений, прежде чем найти нужный результат. Это единственный большой минус одного из старейших численных алгоритмов.