Нахождение нод взаимно простых чисел. Взаимно простые числа: определение, примеры и свойства. Основные свойства взаимно простых чисел

Одинаковых подарков можно составить из 48 конфет «Ласточка» и 36 конфет «Чебурашка», если надо использовать все конфеты?

Решение. Каждое из чисел 48 и 36 должно делиться на число подарков. Поэтому сначала выпишем все делители числа 48.

Получим: 2, 3, 4, 6, 8, 12, 16, 24, 48.

Затем выпишем все делители числа 36.

Получим: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Общими делителями чисел 48 и 36 будут: 1, 2, 3, 4, 6, 12.

Видим, что наибольшим из этих чисел является 12. Его называют наибольший общим делителем чисел 48 и 36.

Значит, можно составить 12 подарков. В каждом подарке будет 4 конфеты «Ласточка» (48:12=4) и 3 конфеты «Чебурашка» (36:12=3).

Содержание урока конспект урока опорный каркас презентация урока акселеративные методы интерактивные технологии Практика задачи и упражнения самопроверка практикумы, тренинги, кейсы, квесты домашние задания дискуссионные вопросы риторические вопросы от учеников Иллюстрации аудио-, видеоклипы и мультимедиа фотографии, картинки графики, таблицы, схемы юмор, анекдоты, приколы, комиксы притчи, поговорки, кроссворды, цитаты Дополнения рефераты статьи фишки для любознательных шпаргалки учебники основные и дополнительные словарь терминов прочие Совершенствование учебников и уроков исправление ошибок в учебнике обновление фрагмента в учебнике элементы новаторства на уроке замена устаревших знаний новыми Только для учителей идеальные уроки календарный план на год методические рекомендации программы обсуждения Интегрированные уроки

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

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

Определение 2 . Самый большой из общих делителей называют наибольшим общим делителем (НОД) .

Пример 1 . Общими делителями чисел 30 , 45 и 60 будут числа 3 , 5 , 15 . Наибольшим общим делителем этих чисел будет

НОД (30 , 45 , 10) = 15 .

Определение 3 . Если наибольший общий делитель нескольких чисел равен 1 , то эти числа называют взаимно простыми .

Пример 2 . Числа 40 и 3 будут взаимно простыми числами, а числа 56 и 21 не являются взаимно простыми, поскольку у чисел 56 и 21 есть общий делитель 7 , который больше, чем 1.

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

Алгоритм нахождения наибольшего общего делителя

Рассмотрим алгоритм нахождения наибольшего общего делителя нескольких чисел на следующем примере.

Пример 3 . Найти наибольший общий делитель чисел 100, 750 и 800 .

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

Простой множитель 2 в первое разложение на множители входит в степени 2 , во второе разложение – в степени 1 , в третье разложение – в степени 5 . Обозначим наименьшую из этих степеней буквой a . Очевидно, что a = 1 .

Простой множитель 3 в первое разложение на множители входит в степени 0 (другими словами, множитель 3 в первое разложение на множители вообще не входит), во второе разложение входит в степени 1 , в третье разложение – в степени 0 . Обозначим наименьшую из этих степеней буквой b . Очевидно, что b = 0 .

Простой множитель 5 в первое разложение на множители входит в степени 2 , во второе разложение – в степени 3 , в третье разложение – в степени 2 . Обозначим наименьшую из этих степеней буквой c . Очевидно, что c = 2 .

В этом статье мы расскажем о том, что такое взаимно простые числа. В первом пункте сформулируем определения для двух, трех и более взаимно простых чисел, приведем несколько примеров и покажем, в каких случаях два числа можно считать простыми по отношению друг к другу. После этого перейдем к формулировке основных свойств и их доказательствам. В последнем пункте мы поговорим о связанном понятии – попарно простых числах.

Что такое взаимно простые числа

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

Определение 1

Взаимно простыми будут два таких числа a и b , наибольший общий делитель которых равен 1 , т.е. НОД (a , b) = 1 .

Из данного определения можно сделать вывод, что единственный положительный общий делитель у двух взаимно простых чисел будет равен 1 . Всего два таких числа имеют два общих делителя – единицу и минус единицу.

Какие можно привести примеры взаимно простых чисел? Например, такой парой будут 5 и 11 . Они имеют только один общий положительный делитель, равный 1 , что является подтверждением их взаимной простоты.

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

Это утверждение иллюстрирует следующий пример: составные числа - 9 и 8 образуют взаимно простую пару. Докажем это, вычислив их наибольший общий делитель. Для этого запишем все их делители (рекомендуем перечитать статью о нахождении делителей числа). У 8 это будут числа ± 1 , ± 2 , ± 4 , ± 8 , а у 9 – ± 1 , ± 3 , ± 9 . Выбираем из всех делителей тот, что будет общим и наибольшим – это единица. Следовательно, если НОД (8 , − 9) = 1 , то 8 и - 9 будут взаимно простыми по отношению друг к другу.

Взаимно простыми числами не являются 500 и 45 , поскольку у них есть еще один общий делитель – 5 (см. статью о признаках делимости на 5). Пять больше единицы и является положительным числом. Другой подобной парой могут быть - 201 и 3 , поскольку их оба можно разделить на 3 , на что указывает соответствующий признак делимости.

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

Пример 1

Условие: выясните, являются ли взаимно простыми числа 275 и 84 .

Решение

Оба числа явно имеют больше одного делителя, поэтому сразу назвать их взаимно простыми мы не можем.

Вычисляем наибольший общий делитель, используя алгоритм Евклида: 275 = 84 · 3 + 23 , 84 = 23 · 3 + 15 , 23 = 15 · 1 + 8 , 15 = 8 · 1 + 7 , 8 = 7 · 1 + 1 , 7 = 7 · 1 .

Ответ: поскольку НОД (84 , 275) = 1 , то данные числа будут взаимно простыми.

Как мы уже говорили раньше, определение таких чисел можно распространить и на случаи, когда у нас есть не два числа, а больше.

Определение 2

Взаимно простыми целые числа a 1 , a 2 , … , a k , k > 2 будут тогда, когда они имеют наибольший общий делитель, равный 1 .

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

Возьмем несколько примеров. Так, целые числа − 99 , 17 и − 27 – взаимно простые. Любое количество простых чисел будет взаимно простым по отношению ко всем членам совокупности, как, например, в последовательности 2 , 3 , 11 , 19 , 151 , 293 и 667 . А вот числа 12 , − 9 , 900 и − 72 взаимно простыми не будут, потому что кроме единицы у них будет еще один положительный делитель, равный 3 . То же самое относится к числам 17 , 85 и 187: кроме единицы, их все можно разделить на 17 .

Обычно взаимная простота чисел не является очевидной с первого взгляда, этот факт нуждается в доказательстве. Чтобы выяснить, будут ли некоторые числа взаимно простыми, нужно найти их наибольший общий делитель и сделать вывод на основании его сравнения с единицей.

Пример 2

Условие: определите, являются ли числа 331 , 463 и 733 взаимно простыми.

Решение

Сверимся с таблицей простых чисел и определим, что все три этих числа в ней есть. Тогда их общим делителем может быть только единица.

Ответ: все эти числа будут взаимно простыми по отношению друг к другу.

Пример 3

Условие: приведите доказательство того, что числа − 14 , 105 , − 2 107 и − 91 не являются взаимно простыми.

Решение

Начнем с выявления их наибольшего общего делителя, после чего убедимся, что он не равен 1 . Поскольку у отрицательных чисел те же делители, что и у соответствующих положительных, то НОД (− 14 , 105 , 2 107 , − 91) = НОД (14 , 105 , 2 107 , 91) . Согласно правилам, которые мы привели в статье о нахождении наибольшего общего делителя, в данном случае НОД будет равен семи.

Ответ: семь больше единицы, значит, взаимно простыми эти числа не являются.

Основные свойства взаимно простых чисел

Такие числа имеют некоторые практически важные свойства. Перечислим их по порядку и докажем.

Определение 3

Если разделить целые числа a и b на число, соответствующее их наибольшему общему делителю, мы получим взаимно простые числа. Иначе говоря, a: НОД (a , b) и b: НОД (a , b) будут взаимно простыми.

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

Определение 4

Необходимым и достаточным условием взаимной простоты чисел a и b является существование таких целых чисел u 0 и v 0 , при которых равенство a · u 0 + b · v 0 = 1 будет верным.

Доказательство 1

Начнем с доказательства необходимости этого условия. Допустим, у нас есть два взаимно простых числа, обозначенных a и b . Тогда по определению этого понятия их наибольший общий делитель будет равен единице. Из свойств НОД нам известно, что для целых a и b существует соотношение Безу a · u 0 + b · v 0 = НОД (a , b) . Из него получим, что a · u 0 + b · v 0 = 1 . После этого нам надо доказать достаточность условия. Пусть равенство a · u 0 + b · v 0 = 1 будет верным, в таком случае, если НОД (a , b) делит и a , и b , то он будет делить и сумму a · u 0 + b · v 0 , и единицу соответственно (это можно утверждать, исходя из свойств делимости). А такое возможно только в том случае, если НОД (a , b) = 1 , что доказывает взаимную простоту a и b .

В самом деле, если a и b являются взаимно простыми, то согласно предыдущему свойству, будет верным равенство a · u 0 + b · v 0 = 1 . Умножаем обе его части на c и получаем, что a · c · u 0 + b · c · v 0 = c . Мы можем разделить первое слагаемое a · c · u 0 + b · c · v 0 на b , потому что это возможно для a · c , и второе слагаемое также делится на b , ведь один из множителей у нас равен b . Из этого заключаем, что всю сумму можно разделить на b , а поскольку эта сумма равна c , то c можно разделить на b .

Определение 5

Если два целых числа a и b являются взаимно простыми, то НОД (a · c , b) = НОД (c , b) .

Доказательство 2

Докажем, что НОД (a · c , b) будет делить НОД (c , b) , а после этого – что НОД (c , b) делит НОД (a · c , b) , что и будет доказательством верности равенства НОД (a · c , b) = НОД (c , b) .

Поскольку НОД (a · c , b) делит и a · c и b , а НОД (a · c , b) делит b , то он также будет делить и b · c . Значит, НОД (a · c , b) делит и a · c и b · c , следовательно, в силу свойств НОД он делит и НОД (a · c , b · c) , который будет равен c · НОД (a , b) = c . Следовательно, НОД (a · c , b) делит и b и c , следовательно, делит и НОД (c , b) .

Также можно сказать, что поскольку НОД (c , b) делит и c , и b , то он будет делить и c , и a · c . Значит, НОД (c , b) делит и a · c и b , следовательно, делит и НОД (a · c , b) .

Таким образом, НОД (a · c , b) и НОД (c , b) взаимно делят друг друга, значит, они являются равными.

Определение 6

Если числа из последовательности a 1 , a 2 , … , a k будут взаимно простыми по отношению к числам последовательности b 1 , b 2 , … , b m (при натуральных значениях k и m), то их произведения a 1 · a 2 · … · a k и b 1 · b 2 · … · b m также являются взаимно простыми, в частности, a 1 = a 2 = … = a k = a и b 1 = b 2 = … = b m = b , то a k и b m – взаимно простые.

Доказательство 3

Согласно предыдущему свойству, мы можем записать равенства следующего вида: НОД (a 1 · a 2 · … · a k , b m) = НОД (a 2 · … · a k , b m) = … = НОД (a k , b m) = 1 . Возможность последнего перехода обеспечивается тем, что a k и b m взаимно просты по условию. Значит, НОД (a 1 · a 2 · … · a k , b m) = 1 .

Обозначим a 1 · a 2 · … · a k = A и получим, что НОД (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = НОД (b 1 · b 2 · … · b m , A) = НОД (b 2 · … · b · b m , A) = … = НОД (b m , A) = 1 . Это будет справедливым в силу последнего равенства из цепочки, построенной выше. Таким образом, у нас получилось равенство НОД (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = 1 , с помощью которого можно доказать взаимную простоту произведений a 1 · a 2 · … · a k и b 1 · b 2 · … · b m

Это все свойства взаимно простых чисел, о которых бы мы хотели вам рассказать.

Понятие попарно простых чисел

Зная, что из себя представляют взаимно простые числа, мы можем сформулировать определение попарно простых чисел.

Определение 7

Попарно простые числа – это последовательность целых чисел a 1 , a 2 , … , a k , где каждое число будет взаимно простым по отношению к остальным.

Примером последовательности попарно простых чисел может быть 14 , 9 , 17 , и − 25 . Здесь все пары (14 и 9 , 14 и 17 , 14 и − 25 , 9 и 17 , 9 и − 25 , 17 и − 25) взаимно просты. Отметим, что условие взаимной простоты является обязательным для попарно простых чисел, но взаимно простые числа будут попарно простыми далеко не во всех случаях. Например, в последовательности 8 , 16 , 5 и 15 числа не являются таковыми, поскольку 8 и 16 не будут взаимно простыми.

Также следует остановиться на понятии совокупности некоторого количества простых чисел. Они всегда будут и взаимно, и попарно простыми. Примером может быть последовательность 71 , 443 , 857 , 991 . В случае с простыми числами понятия взаимной и попарной простоты будут совпадать.

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Проверка ДЗ
Как идет подготовка к
зачету -02.10
и КР - 29.09.

Вопросы к зачету №1. (2 октября 2017 года)
по теме «Делимость чисел» М.6, §1.стр.5-34, мини-рефераты по стр. 33-34 по теме:
«Пифагор», «Решето Эратосфена»
Какое натуральное число называется делителем натурального числа а?
Докажите, что число 4 является делителем числа 24.
Докажите, что число 3 не является делителем числа 25.
Укажите все натуральные делители числа 12.
Какое число является делителем любого натурального числа?
Какое натуральное число называется кратным натурального числа а?
Сколько кратных имеет любое натуральное число?
Какое число является наименьшим из кратных натурального числа?
Какие числа делятся без остатка на 10, а какие не делятся без остатка на 10? Приведите примеры.
Какие числа делятся без остатка на 5, а какие не делятся на 5 без остатка? Приведите примеры.
Какие числа называют четными, а какие числа называют нечетными?
Докажите, что число 8- четное, а число 15 –нечетное.
Назовите четные цифры.
Назовите нечетные цифры.
Какой цифрой должно оканчиваться число, чтобы оно было четным (делилось без остатка на 2), а какой цифрой должно оканчиваться число, чтобы оно
было нечетным? Приведите примеры.
Какое число делится на 9, а какое число на 9 не делится?
Какое число делится на 3, а какое число на 3 не делится?
Какое натуральное число называют простым?
Какое натуральное число называют составным?
Какое число не относят ни к простым, ни к составным?
На сколько и на какие множители можно разложить любое составное число?
Назовите первые 10 простых чисел.
Запишите разложение на множители числа 210.
Всякое ли составное число можно разложить на простые множители?
Является ли следующая запись разложением на простые множители: 2·3·4·5?
Какое натуральное число называют наибольшим общим делителем натуральных чисел а и в?
Какие два числа называют взаимно простыми? Приведите примеры.
Чтобы найти наибольший общий делитель нескольких натуральных чисел, надо….
Найти НОД(16;42)
Какое натуральное число называют наименьшим общим кратным натуральных чисел а и в?
Чтобы найти наименьшее общее кратное нескольких натуральных чисел, надо….
Найти НОК(6;15)
Покажите на примере, что а·в=НОД(а;в)·НОК(а;в)
Контрольная работа № 1 - 29 сентября

Примерный текст КР
Вариант 1.
Вариант 2.
1.Разложите на простые множители число 5544.
1.Разложите на простые множители число 6552.

2.Найдите наибольший общий делитель и
наименьшее общее кратное чисел 504 и 756.
наименьшее общее кратное чисел 1512 и 1008.
3. Докажите, что числа:
3.Докажите, что числа:
а) 255 и 238 не взаимно простые;
а) 266 и 285 не взаимно простые;
б) 392 и 675 взаимно простые.
б) 301 и 585 взаимно простые.
4.Выполните действия: 268,8: 0,56 + 6,44 12.
4.Выполните действия: 355,1: 0,67 + 0,83 15.
5. Может ли разность двух простых чисел быть
5.Может ли сумма двух простых чисел быть

простым числом? (Приведите пример).

Стр. 28,
№
164(1)
Проверка ДЗ

Стр.27. № 164(1).
А
АОВ 180
М
3х
х
Проверка ДЗ
В АОВ АОМ МOВ
О
х+3х=180
4х=180
х=180:4
х=45
ВОМ 45 , АОМ 3 45 135
Ответ: 135°, 45°

Проверка ДЗ
Стр. 28,
б)
№
169(б).
а=2·2·2·3·5·7, в=3·11·13
НОД(а,в)=3

10.

Стр. 28, 170(в,г)
Проверка ДЗ
в) НОД(60,80,48)=2·2=4
60
30
15
5
1
2
2
3
5
80
40
20
10
5
1
2
2
2
2
5
48
24
12
6
3
1
2
2
2
2
3

11.

Проверка ДЗ
Стр. 28, 170(в,г)
г) НОД(195,156,260)=
195 3
65 5
13 13
1
156
78
39
13
1
2
2
3
13
13
260
130
65
13
1
2
2
5
13

12.

Проверка ДЗ
Стр. 28, 171
НОД(861,875)=1
864
432
216
108
54
27
9
3
1
2
2
2
2
2
3
3
3
875
175
35
7
1
5
5
5
7
Числа 861и 875- взаимно простые

13.

Стр. 28,
№
Токари -
3х чел.
Слесари-
2х
174
Проверка ДЗ
чел.
-х чел.
3х+2х+х=840
6х=840
х=840:6
х=140
Фрезировщики
Фрезировщиков-140,
Слесарей-280,
Токарей -420.
Ответ: 420 чел.
Что можно было
не находить?

14. Оцените ДР: - все ответы верны и подробно записано решение «5» - все ответы верны и подробно записано решение, но допущены

вычислительные ошибки
«4»
- ответы верны, но решение либо
неполное, либо его нет совсем
«3»
-домашняя работа отсутствует- «2»

15. 25.09.2017 Классная работа Наибольший общий делитель. Взаимно простые числа.

16. Цели урока:

-Обобщить знания о наибольшем
общем делителе и взаимно простых
числах.
-Развивать умение работать
самостоятельно.
-Учиться выслушивать мнение
других.
- Продолжить формировать
культуру устной и письменной
математической речи.

17.

Работа индивидуально. Остальные
устно и в тетради
Индивидуальная работа по
карточкам

18.

Устный счет
1. Может ли разложение на простые
множители числа 14652
содержать множитель
3?
Почему?
2. Назовите все нечетные числа,
удовлетворяющие неравенству
234<х<243

19.

Устный счет
3.
Назовите 3 числа, кратных:
а) 5; б) 15; в) числу
а
4. Назовите по 2 числа, взаимно
простых с числом:
а) 3,
б) 7,
в) 10,
г) 24

20.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=
8
24
13
26 , 9 , 60 .

21.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=10
НОД(8,24)=
8
24
13
26 , 9 , 60 .

22.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=10
НОД(8,24)=8
НОД(15,35)=
8
24
13
26 , 9 , 60 .

23.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=10
НОД(8,24)=8
НОД(15,35)=5
НОД(13,26)=
8
24
13
26 , 9 , 60 .

24.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=10
НОД(8,24)=8
НОД(15,35)=5
НОД(13,26)=13
НОД(8,9)=
8
24
13
26 , 9 , 60 .

25.

Работа в тетради:
Найдите наибольший общий
делитель числителя и
знаменателя дробей:
20
8
30 , 24 ,
15
35 ,
НОД(20,30)=10
НОД(8,24)=8
НОД(15,35)=5
НОД(13,26)=13
НОД(8,9)=1
НОД(24,60)=
8
24
13
26 , 9 , 60 .

26.

27.

Физкультминутка

28.

Решаем задачу
Стр. 26, №153
Прочитайте задачу.
О ком говорится в задаче?
О чём говорится в задаче?

29.

Решаем задачу
Стр. 26, №153
Можем ли мы ответить сразу на
1 вопрос:
Сколько было автобусов?

30.

Решаем задачу
Стр. 26, №153
Как найти сколько было
пассажиров в каждом автобусе?