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

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

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

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

При поиске НОД, например 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) = 23}$$

В каждом автобусе было по 23 места. В лес поехало 8 автобусов, а на озеро поехало 6 автобусов. Всего было 8 + 6 = 14 автобусов.

У меня есть дополнительная информация к этой части урока!

Закрыть

Алгоритм Евклида- простой и удобный способ нахождения НОДа двух целых чисел. Правило названо в честь известного греческого математика Евклида, жившего в III веке до нашей эры. Он впервые описал данный алгоритм в VII и X книгах «Начал» своего фундаментального математического сборника трудов. Считается практически самым старым из численных правил, который дошел до нас и до сих пор используется в первозданном виде.

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

11

Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной.

Пройти тест
Закрыть тест

Пройти тест и получить оценку можно после входа или регистрации

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

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

Число 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

Числа 257 являются взаимно простыми (так как их НОД равен 1). Проверим, будет ли делиться 420 на произведение взаимно простых чисел 25 и 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)}\)

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

Заключительный тест

Пройти тест