6 наибольший общий делитель взаимно простые числа. Взаимно простые числа – определение, примеры и свойства

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

Навигация по странице.

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

Пример.

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

Решение.

Очевидно, что данные числа не являются простыми, поэтому мы не можем сразу говорить о взаимной простоте чисел 84 и 275 , и нам придется вычислять НОД. Используем алгоритм Евклида для нахождения НОД : 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 . Этим доказано, что числа 84 и 275 взаимно простые.

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

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

Целые числа a 1 , a 2 , …, a k , k>2 называются взаимно простыми , если наибольший общий делитель этих чисел равен единице.

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

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

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

Пример.

Являются ли числа 331 , 463 и 733 взаимно простыми?

Решение.

Заглянув в таблицу простых чисел, мы обнаружим, что каждое из чисел 331 , 463 и 733 – простое. Следовательно, они имеют единственный положительный общий делитель – единицу. Таким образом, три числа 331 , 463 и 733 есть взаимно простые числа.

Ответ:

Да.

Пример.

Докажите, что числа −14 , 105 , −2 107 и −91 не являются взаимно простыми.

Решение.

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

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

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

Взаимно простые числа обладают рядом свойств. Рассмотрим основные свойства взаимно простых чисел .

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

Это свойство мы доказали, когда разбирали свойства НОД .

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

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

Докажем сначала необходимость.

Пусть числа a и b взаимно простые. Тогда по определению взаимно простых чисел НОД(a, b)=1 . А из свойств НОД мы знаем, что для целых чисел 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, b) в силу свойств делимости должен делить сумму a·u 0 +b·v 0 , а значит, и единицу. А это возможно только когда НОД(a, b)=1 . Следовательно, a и b – взаимно простые числа.

Следующее свойство взаимно простых чисел таково: если числа a и b взаимно простые, и произведение a·c делится на b , то c делится на 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 , следовательно, вся сумма делится на b . А так как сумма a·c·u 0 +b·c·v 0 равна c , то и c делится на b .

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

Покажем, во-первых, что НОД(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 , а так как он делит с , то также делит и a·c . Таким образом, НОД(c, b) делит и a·c и b , следовательно, делит и НОД(a·c, b) .

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

Если каждое из чисел 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 – взаимно простые числа.

Предыдущее свойство взаимно простых чисел позволяет нам записать ряд равенств вида НОД(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 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 являются взаимно простыми числами.

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

Попарно простые числа – определения и примеры

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

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

Целые числа 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 не взаимно простые. Однако, числа 8 , 16 , 5 и 15 – взаимно простые. Таким образом, 8 , 16 , 5 и 15 – взаимно простые числа, но не попарно простые.

Следует особо выделить совокупность некоторого количества простых чисел. Эти числа всегда являются и взаимно простыми и попарно простыми. Например, 71 , 443 , 857 , 991 – и попарно простые, и взаимно простые числа.

Также понятно, что когда речь идет о двух целых числах, то для них понятия «попарно простые» и «взаимно простые» совпадают.

Список литературы.

• Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
• Виноградов И.М. Основы теории чисел.
• Михелович Ш.Х. Теория чисел.
• Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.

Назад Вперёд

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

Данная работа предназначена для сопровождения объяснения новой темы. Практические и домашние задания учитель подбирает на свое усмотрение.

Оборудование: компьютер, проектор, экран.

Ход объяснения

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

Устная работа.

1. Вычислите:

а) 0,7 * 10 : 2 - 0,3 : 0,4 _________ ?

б) 5 : 10 * 0,2 + 2 : 0,7 _______ ?

Ответы: а) 8; б) 3.

2. Опровергните утверждение: Число “2” является общим делителем всех чисел”.

Очевидно, что нечетные числа не делятся на 2.

3. Как называются числа, кратные 2?

4. Назовите число, которое является делителем любого числа.

Письменно.

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

2. Найдите все общие делители чисел 18 и 60.

Назовите наибольший общий делитель чисел 18 и 60.

Попробуйте сформулировать, какое число называют наибольшим общим делителем двух натуральных чисел

Правило. Наибольшее натуральное число, на которое делятся без остатка числа , называют наибольшим общим делителем.

Пишут: НОД (18; 60) = 6.

Скажите, пожалуйста, удобен ли рассмотренный способ нахождения НОД?

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

Давайте попытаемся найти другой способ нахождения НОД.

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

18 =

Приведите примеры делителей числа 18.

Числа: 1; 2; 3; 6; 9; 18.

Приведите примеры делителей числа 60.

Числа: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30; 60.

Приведите примеры общих делителей чисел 18 и 60.

Числа: 1; 2; 3; 6.

Как можно найти наибольший общий делитель 18 и 60?

Алгоритм.

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

2. Сравнить множители чисел и вычеркнуть разные.

3. Вычислить произведение оставшихся множителей.

Слайд 4. Взаимно простые числа.

Задание. Найдите НОД чисел 24 и 35.

Правило. Натуральные числа называются взаимно простыми, если их наибольший общий делитель равен 1.

Это интересно!

• Делители числа 18: 1; 2; 3; 6; 9; 18.
• Делители числа 60: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30; 60.
• НОД (18;60) = 6.
• Делители числа 6: 1; 2; 3; 6.
• Заметим, что числа 1; 2; 3; 6 являются общими делителями чисел 18 и 60.
• Например, НОД (108;196) = 4. Значит, сразу можно сказать, что общие делители чисел 108 и 196 – это делители числа 4, то есть 1; 2; 4.

Каждый делитель числа НОД (a;b) является общим делителем чисел a и b и, наоборот, каждый их общий делитель является делителем числа НОД (a;b).

Учебники математики порой сложны для восприятия. Сухой и четкий язык авторов не всегда доступен для понимания. Да и темы там всегда взаимосвязанные, взаимовытекающие. Для освоения одной темы приходится поднимать ряд предыдущих, а порой и перелистывать весь учебник. Сложно? Да. А давайте рискнем обойти эти сложности и попробуем найти к теме не совсем стандартный подход. Сделаем эдакий экскурс в страну чисел. Определение, однако, мы все-таки оставим прежним, ибо правила математики отменить нельзя. Итак, взаимно простые числа — числа натуральные, с общим делителем, равным единице. Это понятно? Вполне.

Для более наглядного примера давайте возьмем числа 6 и 13. И то, и другое — делимы на единицу (взаимно простые). А вот числа 12 и 14 — таковыми не могут являться, поскольку делятся не только на 1, но и на 2. Следующие числа — 21 и 47 тоже не подходят к категории "взаимно простые числа": их можно разделить не только на 1, но еще и на 7.

Обозначают взаимно простые числа так: (а , у) = 1.

Можно сказать даже проще: общий делитель (наибольший) здесь равен единице.
Для чего нам такие знания? Причин достаточно.

Взаимно включены в некоторые системы шифрования. Те, кто работает с шифрами Хилла или с системой подстановок Цезаря, понимают: без этих знаний — никуда. Если вы слышали о генераторах то вряд ли решитесь отрицать: взаимно простые числа используются и там.

Теперь поговорим о способах получения таких простые, как вы понимаете, могут иметь лишь два делителя: они делимы на самих себя и на единицу. Скажем, 11, 7, 5, 3 — числа простые, а вот 9 — нет, ведь это число уже делимо и на 9, и на 3, и на 1.

И если а — число простое, а у - из множества {1, 2, ... а - 1}, то тогда гарантированно (а , у ) = 1, или взаимно простые числа — а и у .

Это, скорее, даже не объяснение, а повторение или подведение итогов только что сказанного.

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

Можно работать путем подбора у > а . Для этого у выбирается так, чтобы число на а не делилось. Для этого число простое умножается на число натуральное и прибавляется (или, напротив, вычитается) величина (допустим, р ), которая меньше а :

у = р а + k

Если, например, а = 71, р = 3, q=10, то, соответственно, у здесь будет равен 713. Возможен и другой подбор, со степенями.

Составные числа, в отличие от взаимно простых, делятся и на себя, и на 1, и на другие числа (тоже без остатка).

Другими словами, (кроме единицы) разбиты на составные и простые.

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

Самое большое простое число найдено доктором-офтальмологом Мартином Новаком, участвовавшим в проекте GIMPS (распределительные вычисления) вместе с другими энтузиастами, которых насчитывалось около 15 тыс. На расчеты ушло шесть долгих лет. Было задействовано два с половиной десятка компьютеров, находящихся в глазной клинике Новака. Результатом титанического труда и упорства явилось число 225964951-1, с записыванием в 7816230-десятичных знаках. Кстати, рекорд самого большого числа был поставлен за полгода до этого открытия. И знаков там было на полмиллиона меньше.

У гения, желающего назвать число, где продолжительность десятичной записи "перепрыгнет" десятимиллионную отметку, есть шанс получить не только всемирную славу, но и 100 000 долларов. Кстати, за число, преодолевшее миллионный рубеж знаков, Наян Хайратвал получил меньшую сумму (50 000 долларов).