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


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



бет4/24
Дата03.01.2022
өлшемі186.94 Kb.
#451024
түріЛекции
1   2   3   4   5   6   7   8   9   ...   24
17. Лекция по элементарной математике

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


Определение 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, что
  1. 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 делится



на m
(a, b)

, а потому M



Свойство 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]






Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   24




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет