§ 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. Если произведение двух чисел a b делится на с и а

взаимно просто с с, то 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

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

§ 5 Наименьшее общее кратное (НОК)

Определение 1. Пусть

a₁,..., a_n

– целые числа, отличные от нуля.

Целое число М называется общим кратным этих чисел, если оно де- лится на каждое из данных чисел.

Например, произведение a₁

сомножителей.

– общее кратное всех своих

Определение 2. Целое число т называется наименьшим общим кратным чисел a₁,..., a_n , если оно является их общим кратным и если любое общее кратное этих чисел делится на т.

Покажем, что если наименьшее общее кратное чисел a₁,..., a_n суще- ствует, то оно однозначно определено с точностью до знака. В самом

деле, пусть т₁ и т₂ – наименьшие общие кратные чисел

a₁,..., a_n . То-

гда по определению 2 должны выполняться соотношения m₁ и

m₂ m₁ . Эти соотношения могут выполняться лишь при условии, что т₁

= т₂ или т₁ = – т₂.

В дальнейшем мы будем выбирать положительное значение наи- меньшего общего кратного и обозначать его так:

Докажем следующую теорему:

Теорема 1. Число
(a, b)

где (a, b) – наибольший общий дели-

тель двух натуральных чисел а и b, является наименьшим общим кратным этих чисел.

Доказательство. Пусть (a,b) , тогда a nl и b ld, ,

где (n,l) Следовательно,

(a, b) d

Это равенство показывает, что ляется общим кратным чисел а и b.
(a, b)
делится на а и на b, т.е. яв-

Покажем теперь, что любое кратное М > 0 чисел а и b делится

на

(a, b)

. В самом деле, M

и потому существует такое целое

число s, что

13. as nds.

Поскольку M b и b

то nds ld , и

потому

ns l. . Но (n,l ) 1, и потому в силу теоремы 3 § 3

s l. Зна-

nds = ndlk и, поскольку
(a, b)

число М делится на

.

(a, b)

Мы показали, что m

а и b.

Теорема доказана.

(a, b)

• 
  наименьшее общее кратное чисел
  

Следствие 1. Любые два отличные от нуля целые числа имеют наи- меньшее общее кратное.

В самом деле, этим наименьшим общим кратным является число

a, b

(a, b)

Следствие 2. Наименьшее общее кратное двух чисел а и b

(a является наименьшим по -величине положительным

общим кратным этих чисел.

В самом деле, Любое общее кратное М > 0 чисел а и b делится

на m
(a, b)

, а потому M

Свойство 1. Если каждое из чисел а и b умножить на одно и то же число k то их НОК умножится на k.

Действительно:

ak bk abk ² a b

ak,bk k.

(ak,bk) (a,b)k (a,b)
Свойство 2. Если a и mo
Доказательство аналогично доказательству свойства 1.

Теорема 2. Если [a₁,..., a_n

и [ , a_n ]

m, то

[a₁,..., a_n ]

Д о к а з а т е л ь с т в о . Число [ , a_n ] m, делится на а_п и на

. Но делится на каждое из чисел

a₁,..., a_{n 1} . Поэтому т делится

на любое из чисел ^a₁^{,..., a}_n

т. е. является их общим кратным.

Пусть М – общее кратное чисел

^a₁^{,..., a}_n . Тогда М делится на

числа a₁,..., a_{n 1}, , а значит, и на ^[a₁^{,..., a}_n

. Так как М делится и

на а_п, то М делится на [ , a_n ]

m . Этим доказано, что т – наимень-

шее общее кратное чисел a₁,..., a_n . Из теоремы 2 точно так же, как и в случае наибольшего общего делителя, вытекает следующее утвержде- ние:

Теорема 3. Если [a₁, a₂ ]

то [a₁,..., a_n ]

[m_n

Пример1. Найти наименьшее общее кратное чисел 546 и 231.

[546, 231]

546 231 _.

(546, 231)

Для этого необходимо найти наи-

больший общий делитель данных чисел 546 и 231. И он будет равен последнему не нулевому остатку в алгоритме Евклида.

					546	231
					462	2
	231				84
	168				2
84		63
63		1
63	21
63	3
0

(546, 231)

[546, 231]

Ответ: [546, 231]