Определение 1. Если НОД зываются взаимно простыми.
( a1 ,..., an ) 1, , то числа
a1,..., an
на-
Например, числа 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
числа a1 и b1 взаимно просты.
и b b1 , то
В самом деле, так как ( a, b) 1, то найдутся такие целые числа х и
у, что ах + by = 1. Но по условию а = a1q, b = b1t, а потому
а1 ( qx)
Это равенство показывает, что a1 и b1 взаимно просты.
Теорема 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 = abq1, т. е. с делится на 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. Если любая пара чисел, составленная из чисел
a1,..., an взаимно проста, то числа
имно простыми.
a1,..., an
называют попарно вза-
§ 5 Наименьшее общее кратное (НОК)
Определение 1. Пусть
a1,..., an
– целые числа, отличные от нуля.
Целое число М называется общим кратным этих чисел, если оно де- лится на каждое из данных чисел.
Например, произведение a1
сомножителей.
– общее кратное всех своих
Определение 2. Целое число т называется наименьшим общим кратным чисел a1,..., an , если оно является их общим кратным и если любое общее кратное этих чисел делится на т.
Покажем, что если наименьшее общее кратное чисел a1,..., an суще- ствует, то оно однозначно определено с точностью до знака. В самом
деле, пусть т1 и т2 – наименьшие общие кратные чисел
a1,..., an . То-
гда по определению 2 должны выполняться соотношения m1 и
m2 m1 . Эти соотношения могут выполняться лишь при условии, что т1
= т2 или т1 = – т2.
В дальнейшем мы будем выбирать положительное значение наи- меньшего общего кратного и обозначать его так:
Докажем следующую теорему:
Теорема 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, что
as nds.
Поскольку M b и b
то nds ld , и
потому
ns l. . Но (n,l ) 1, и потому в силу теоремы 3 § 3
s l. Зна-
чит, существует такое натуральное число k, что s = lk. Но тогда М =
nds = ndlk и, поскольку
( a, b)
число М делится на
.
(a, b)
Мы показали, что m
а и b.
Теорема доказана.
( a, b)
наименьшее общее кратное чисел
Следствие 1. Любые два отличные от нуля целые числа имеют наи- меньшее общее кратное.
В самом деле, этим наименьшим общим кратным является число
a, b
(a, b)
Следствие 2. Наименьшее общее кратное двух чисел а и b
(a является наименьшим по -величине положительным
общим кратным этих чисел.
В самом деле, Любое общее кратное М > 0 чисел а и b делится
Свойство 1. Если каждое из чисел а и b умножить на одно и то же число k то их НОК умножится на k.
Действительно:
ak bk abk 2 a b
ak, bk k.
( ak, bk) ( a, b) k ( a, b)
Свойство 2. Если a и mo
Доказательство аналогично доказательству свойства 1.
Теорема 2. Если [ a1,..., an
и [ , an ]
m, то
[a1,..., an ]
Д о к а з а т е л ь с т в о . Число [ , an ] m, делится на ап и на
. Но делится на каждое из чисел
a1,..., an 1 . Поэтому т делится
на любое из чисел a1,..., an
т. е. является их общим кратным.
Пусть М – общее кратное чисел
a1,..., an . Тогда М делится на
числа a1,..., an 1, , а значит, и на [a1,..., an
. Так как М делится и
на ап, то М делится на [ , an ]
m . Этим доказано, что т – наимень-
шее общее кратное чисел a1,..., an . Из теоремы 2 точно так же, как и в случае наибольшего общего делителя, вытекает следующее утвержде- ние:
Теорема 3. Если [ a1, a2 ]
то [ a1,..., an ]
[mn
Пример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]
Достарыңызбен бөлісу: |