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

Два натуральных числа называют взаимно простыми, если единственным их общим делителем является 1, или, что то же самое, их наибольший общий делитель равен 1. Учитывая основную теорему арифметики, можно сказать, что два натуральных числа взаимно просты тогда и только тогда, когда они не имеют общих простых делителей.
взаимно простые числа
Заметьте, например, что числа 4 и 9 взаимно просты, но по отдельности ни одно из них не является простым. А число 1 взаимно просто с любым числом, в том числе и с самим собой.

Для этого определения совершенно несущественно, что чисел только два — оно буквально переносится на любое количество натуральных чисел. Например, числа 6, 10, 15 взаимно просты, хотя никакие два из них взаимно простыми, очевидно, не являются.

Свойство взаимной простоты переносится и на множество целых чисел. При этом исходное определение — для натуральных чисел — естественным образом корректируется: целое число всегда имеет два делителя — 1 и -1, так что два целых числа называются взаимно простыми, если их общими делителями являются только 1 и -1.

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

Отметим также, что иногда встречается не совсем аккуратная формулировка типа «два числа — натуральных или целых — называются взаимно простыми, если они не имеют общих делителей». В этом случае как бы забывается о 1 и -1. Такая «забывчивость» оправдана тем, что 1 и -1 — тривиальные делители, они всегда есть, и эту мелочь можно для краткости лишь подразумевать.

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

Напомним, что целое число называют простым, если простым числом является его модуль — натуральное число. Такое обобщение школьного понятия простого числа вполне естественно: ведь главное — это возможность разумного, нетривиального разложения числа на множители, а с этой точки зрения числа, скажем, 5 и -5 вполне равноправны: разложение -5 = (-5) неинтересно, неразумно, тривиально.

Для взаимно простых целых чисел чрезвычайно важным и полезным с точки зрения задач является следующий критерий взаимной простоты двух целых чисел: целые числа a и b взаимно просты тогда и только тогда, когда существуют такие целые числа u и v, что au+ bv = 1.

Это свойство, однако, явно неверно, если говорить только о натуральных числах: очевидно, не существует таких натуральных чисел u и v, что 2u + Зv = 1.

На основании именно этого свойства можно доказать — независимо от основной теоремы, что если произведение двух целых чисел делится на простое число р, то хотя бы одно из этих чисел делится на р. В самом деле, если а не делится на р, то а и р взаимно просты, а тогда для некоторых u и v выполняется равенство au + рv = 1, откуда abu + bрv = b, так что b делится на р.

Более того, это утверждение в действительности является главным для доказательства основной теоремы арифметики.

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

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

Материалы по теме:
Поделиться с друзьями:
Оцените материал:
1 Star2 Stars3 Stars4 Stars5 Stars (2 голосов, рейтинг: 3,50 с 5)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *