$p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.

Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.

Пример 1

Найти делители числа $6$.

Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3, 6$. Значит делителем числа $6$ будут числа $1,2,3,6.$

Ответ: $1,2,3,6$.

Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.

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

Составным называют число, у которого кроме единицы и самого себя есть другие делители.

Примером простого числа может являться число $13$, примером составного число $14.$

Замечание 1

Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.

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

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

Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД и сравнить его с $1$.

Попарно взаимно простые

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

Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми . Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.

Пример 2

$8, 15$ - не простые, но взаимно простые.

$6, 8, 9$ - взаимно простые числа, но не попарно взаимно простые.

$8, 15, 49$ - попарно взаимно простые.

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

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

Например, разложим на простые множители число $180$:

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$

Воспользуемся свойством степеней, тогда получим,

$180=2^2\cdot 3^2\cdot 5$

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

Каноническое разложение натурального числа в общем виде

Каноническое разложение натурального числа в общем виде имеет вид:

$m=p^{n1}_1\cdot p^{n2}_2\cdot \dots \dots ..\cdot p^{nk}_k$

где $p_1,p_2\dots \dots .p_k$- простые числа, а показатели степеней- натуральные числа.

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

Пример 3

Найти наибольший общий делитель чисел $180$ и $240$.

Решение: Разложим числа на простые множества с помощью канонического разложения

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тогда $180=2^2\cdot 3^2\cdot 5$

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тогда $240=2^4\cdot 3\cdot 5$

Теперь найдем НОД этих чисел, для этого выберем степени с одинаковым основанием и с наименьшим показателем степени, тогда

$НОД \ (180;240)= 2^2\cdot 3\cdot 5=60$

Составим алгоритм нахождения НОД с учетом канонического разложения на простые множители .

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

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

Пример 4

Определить, будут ли простыми, взаимно простыми числами числа $195$ и $336$.

$195=3\cdot 5\cdot 13$

$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

$НОД \ (195;336) =3\cdot 5=15$

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

Пример 5

Определить, будут ли простыми, взаимно простыми числами числа $39$ и $112$.

Решение: Воспользуемся для разложения на множители каноническим разложением:

$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

$НОД \ (39;112)=1$

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

Пример 6

Определить будут ли простыми, взаимно простыми числами числа $883$ и $997$.

Решение: Воспользуемся для разложения на множители каноническим разложением:

$883=1\cdot 883$

$997=1\cdot 997$

$НОД \ (883;997)=1$

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

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

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

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

Пример.

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

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

Для более наглядного примера давайте возьмем числа 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 долларов).

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

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

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

Определение 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

Определение1 . Целые числа а 1 ,а 2 ,…,a k называются взаимно-простыми, если (а 1 ,а 2 ,…,a k) =1

Определение 2. Целые числа а 1 ,а 2 ,…,a k называются попарно взаимно-простыми, если i,s (i, s = 1, 2, .. , к, is, (а i , а s) =1).

Если числа удовлетворяют определению 2, то они удовлетворяют и определению 1. Обратное утверждение в общем случае неверно, например: (15, 21, 19)= 1, но (15, 21) = 3

Теорема (критерий взаимной простоты)

(а, b) = 1 <=>  х, у Z: ах + by = 1

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

Докажем необходимость. Пусть (а, b) = 1. Выше мы показали, что если d=(a,b), то  х, y Z: d = ax +by.

Т.к. в этом случае d =1, то будут  х, y Z (определяемые из алгоритма Евклида): 1 = ах + bу.

Достаточность. Пусть (*) ах + by = 1, докажем, что (а, b)=1. Предположим, что (a, b) = d, тогда в левой части равенства (*)

(a / d) & (b /d) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.

§4. Нок целых чисел и его свойства.

Определение 1. Общим кратным конечного множества целых чисел а 1 ,а 2 ,…,a k , отличных от нуля, называют целое число m, которое делится на все числа a i (i=l, 2,…, к)

Определение 2. Целое число (m) называется наименьшим общим кратным чисел а 1 ,а 2 ,…,a k , отличных от нуля, если:

1 m - является их общим кратным;

2 (m) делит любое другое общее кратное этих чисел.

Обозначение: m = НОК (а 1 ,а 2 ,…,a k) или m = [а 1 ,а 2 ,…,a k ]

Пример. Даны числа: 2, 3, 4, 6, 12.

Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.

НОК определяется однозначно с точностью до порядка следования сомножителей. Действительно, если предположить, что m 1 = [а, b] &m 2 =  (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Между наименьшим общим кратным и наибольшим общим делителем двух целых чисел существует зависимость, которая выражается формулой: [а, b] = ab/(а, b) (выведите ее самостоятельно)

Эта связь позволяет утверждать, что для любой пары целых чисел, отличных от нуля, существует их наименьшее общее кратное. Действительно, (а, b) – всегда можно однозначно вывести из алгоритма Евклида и по определению (а, b)  0, тогда дробь ab/(а, b)  0 и будет определена однозначно.

Наиболее просто НОК двух целых чисел вычисляется в том случае, когда (а,b)= 1, тогда [а, b] = ab/1 = а b

Например, = 215/1 = 105, т. к. (21, 5) = 1.

§5. Простые числа и их свойства.

Определение 1. Натуральное число (р) называется простым, если р > 1 и не имеет положит. делителей, отличных от 1 и р.

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

Из этих определений следует, что множество натуральных чисел можно разбить на три класса:

а) составные числа;

б) простые числа;

в) единица.

Если а - составное, то а = nq, где 1

Задача 1. Доказать, что если aZ и р - простое число, то (а, р) = 1 v (a / р)

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

Пусть d = (а, р) => (a /d) & (р /d), т.к. р - простое число, то оно имеет два делителя 1 и р. Если (а, р) = 1, то а и р взаимно просты, если (а, р) = р, то (а/р).

Задача 2. Если произведение нескольких сомножителей делится на р, то по крайней мере один из сомножителей делится на р.

Решение.

Пусть произведение (а 1 ,а 2 ,..., а k)/р, если все a i не будут делиться на р, тогда и произведение будет взаимно просто с р, следовательно, какой-то сомножитель делится на р.

Задача 3. Доказать, что наименьший отличный от 1 делитель целого числа а>1, есть число простое.

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

Пусть aZ и а - составное число (если а = р, то утверждение доказано), тогда а = a 1 q.

Пусть q - наименьший делитель, покажем, что он будет простым числом. Если предположить, что q - составное число, тогда q = q 1 k и а = a 1 q 1 k, т.к. q 1

Задача 4. Доказать, что наименьший простой делитель (р) натурального числа (n) не превосходит n .

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

Пусть n = рn 1 , причем р < n 1 и р - простое. Тогда n  р 2 => р<n .

Из этого утверждения следует, что если натуральное число (n) не делится ни на одно простое число р n , то n – простое, в противном случае оно будет составным.

Пример 1 . Выяснить, будет ли число 137 простым? 11 <137 <12.

Выписываем простые делители, не превосходящие 137: 2, 3, 5, 7, 11. Проверяем, что 137 не делится на 2, на 3, на 5, на 7, на 11. Следовательно, число 137 – простое.

Теорема Евклида . Множество простых чисел бесконечно.

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

Предположим противное, пусть p 1 ,p 2 ,..., p k все простые числа, где p 1 = 2, а p k – самое большое простое число.

Составим натуральное число  = p 1 p 2 ... p к +1, т.к.  p i , то оно должно быть составным, тогда его наименьший делитель будет простым (см. задачу 3). Однако  не делится ни на p 1 , ни на p 2 ,…, ни на p k , т.к. 1 не делится на любое p I .

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

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

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

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

Возьмём произвольное натуральное число (n) и составим последовательность натуральных чисел (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1).

В этой последовательности каждое последующее число на 1 больше предыдущего, все эти числа составные, т.к. каждое имеет более двух делителей (например, первое число делится на 1, на 2 и само на себя). При n→∞ мы получим сколь угодно длинный интервал, состоящий только из составных чисел.

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

Основная теорема арифметики

Любое натуральное число n>1 может быть представлено единственным образом в виде произведения простых чисел, с точностью до порядка следования сомножителей.

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

Докажем возможность представления:

Пусть nN и n>1, если n – простое число, то n = p и теорема доказана. Если n – составное, то наименьший его делитель будет числом простым и n = p 1 n 1 , где n 1

Далее рассуждаем аналогично. Если n 1 простое число, то теорема доказана, если n 1 составное число, то n 1 = p 2 n 2 , где n 2 < n 1 и тогда n = p 1 p 2 n 2 . На каком-то шаге получим n = p 1 p 2 …p n , где все p i - простые числа.

Докажем единственность разложения:

Предположим, что для числа (n) есть два различных представления: n = p 1 p 2 …p k , n = q 1 q 2 …q n и n>k.

Тогда получим, что p 1 p 2 …p k = q 1 q 2 …q n (1). Левая часть равенства (1) делится на p 1 , тогда по свойству простых чисел (см. задача 2), по крайней мере, один из сомножителей правой части должен делиться на p 1 .

Пусть (q 1 /p 1) => (q 1 =p 1). Разделив обе части равенства (1) на p 1 , получим равенство p 2 p 3 …p k = q 2 q 3 …q n . Повторяя прежнее рассуждение ещё (k-1) раз, мы получим равенство 1 = q k +1 q k +2 …q n , т.к. все q i >1, то это равенство невозможно. Следовательно, в обеих разложениях число сомножителей одинаково (k=n) и сами сомножители одинаковы.

Замечание. В разложении числа (n) на простые сомножители некоторые из них могут повторяться. Обозначая буквами  1 , 2 ,…, k кратность их вхождения в (n), получим так называемое каноническое разложение числа (n):

Пример 2.

Каноническое разложение числа 588000 = 2 5 35 3 7 2

Следствие 1. Если
тогда все делители числа (n) имеют вид:
где 0 i  i (i = 1, 2,…,k).

Пример 3. Все делители числа 720 = 2 4 3 2 5 получим, если в выражении
вместо 1 ,  2 ,  3 , независимо друг от друга, будем подставлять значения:  1 =0, 1, 2, 3, 4,  2 =0, 1, 2,  3 = 0, 1.

Искомые делители будут равны: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; 9; 18; 36; 72; 144; 5; 10; 20; 40; 80; 15; 30; 60; 120; 240; 45; 90; 180; 360; 720.

Следствие 2. Если
и
то (a, b) = p 1  1 p 2  2 …p k  k , где i = min( I ,  i)

P 1  1 p 2  2 …p k  k , где i = max( I ,  i).

Пример 4. Найти НОД(a, b) и НОК(a, b), используя каноническое разложение, если

(24, 42) = 23 = 6