17. Лекция по элементарной математике. Лекции по элементарной математике Глава Элементы теории чисел 5 Метод математической индукции 5

• Название: Лекции по элементарной математике Глава Элементы теории чисел 5 Метод математической индукции 5
• Дата: 30.03.2021
• Размер: 186.94 Kb.
• Имя файла: 17. Лекция по элементарной математике.docx
• Тип: Лекции; #189455
• страница: 4 из 25

§ 4. Взаимно простые числа и их основные свойства

Определение 1. Если НОД зываются взаимно простыми.

(a₁ ,..., a_n) 1, , то числа

a₁,..., a_n

на-

Например, числа 30 и 77 взаимно просты, поскольку (30,77) = 1, а

числа 30 и 72 не являются взаимно простыми, так как (30,72) = 6.

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

Теорема 1. Для того чтобы числа а и b были взаимно простыми, необходимо и достаточно, чтобы существовали такие целые числа х и у, что

ax (1)

Необходимость. Если числа а и b взаимно просты, то (a, b) 1. Тогда (по теореме 6 предыдущего параграфа) существуют такие це- лые числа х и у, что имеет место равенство (1).

Достаточность. Пусть существуют такие целые числа х и у, что

имеет место равенство (1), и пусть (a, b) = d. Тогда (согласно свойству 4 делимости) из (1) следует, что 1 d . Значит, d = 1, т. е. числа а и b взаимно просты.

Следствие. Если числа а и b взаимно просты и a

числа a₁ и b₁ взаимно просты.

и b b₁ , то

В самом деле, так как (a, b) 1, то найдутся такие целые числа хи

у, что ах + by = 1. Но по условию а = a₁q, b = b₁t, а потому

а₁ (qx)

Это равенство показывает, что a₁ и ^b₁ взаимно просты.

Теорема 2. Частные от деления чисел a u b на (a, b) взаимно про- сты.

Пусть (a, b) = d. Тогда существуют такие целые числа х и у, что ах

+ by = d. Разделив обе части этого равенства на d, получим:

a _x

d d

Следовательно

т. е. числа ^a и ^b

d d

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

Теорема 3. Если произведение двух чисел ab делится на с и а

взаимно просто с с, то b делится на с.

Так как (а, с) = 1, то существуют такие целые числа х и у, что ах+

су = 1.

Умножая обе части этого равенства на b, получим:

abx + cby = b. По условию ab c , следовательно, левая часть по- следнего равенства (согласно свойству 4 делимости) делится на с; то- гда и правая часть тоже делится на с, т.е.

Теорема 4. Если числа a u b взаимно просты, то число с делится

на ab тогда и только тогда, когда с делится на а и на b.

Необходимость. Так как с делится на ab и ab делится на а и на b,

то с делится на а и на b.

Достаточность. Если с делится на а, то с = aq. Но с делится на b, а числа а и b взаимно просты. В силу теоремы 3 получаем, что q де- лится на b. Но тогда с = aq = abq₁, т. е. с делится на ab.

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

Теорема 5. Если два числа a u b взаимно просты с третьим числом с, то и их произведение взаимно просто с с.

Доказательство. Проведем доказательство от противного. Предпо-

ложим, что (ab,с) = d> 1. Тогда Так как по условию (а, с) = 1,

то по следствию из теоремы 1 и (a,d) = 1. Поскольку ab и (a, d) =

1, то по теореме 3 b d.. Значит, d является общим делителем чисел b и с, а это противоречит предположению о том, что эти числа взаимно просты. Полученное противоречие и доказывает, что (ab, с) = 1.

Определение 2. Если любая пара чисел, составленная из чисел

a₁,..., a_n взаимно проста, то числа

имно простыми.

a₁,..., a_n

называют попарно вза-