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

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

§ 3. Наибольший общий делитель. Алгоритм Евклида

1. 
   Наибольший общий делитель (НОД). Введем следующие оп- ределения:
   

Определение 1. Целое число называется общимделителем,

целых чисел a₁, a₂ ,..., a_n , если каждое из этих чисел делится на .

Определение 2. Целое число d называется наибольшим общим де- лителем чисел a₁, a₂ ,..., a_n если:

1. 
   d является общим делителем этих чисел;
   
2. 
   d делится на любой общий делитель чисел a₁, a₂ ,..., a_n .
   

Теорема 1. Наибольший общий делитель чисел

a₁,..., a_n

определен

однозначно с точностью до знака (иными словами, если

d₁ и d₂ –

наибольшие общие делители чисел

d₁

a₁,..., a_n , то либо d₁

d₂ , либо

Доказательство. Пусть

d₁ и d₂

– наибольшие общие делители чи-

сел

a₁,..., a_n . Так как d₁

– наибольший общий делитель, то он делит-

ся на любой общий делитель этих чисел, а значит, делится на d₂. Точно

так же доказываем, что

^d₂ ^d₁ . Но отношения

^d₁ ^d₂ и

^d₂ ^d₁ могут

иметь место лишь в случае, когда ^d₁

^d₂ или ^d₁

d₂ ).

Условимся всегда брать положительное значение наибольшего об-

щего делителя чисел

a₁,..., a_n . Это значение будем обозначать

Пример1. Наибольший общий делитель чисел 135 и –180 равен

45. 
    В самом деле, множество положительных делителей числа 135 име- ет вид:
    

А = {1, 3, 5, 9, 15, 27, 45, 135},

а для числа – 180 – вид:

В = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}.

Пересечением этих множеств является

A B ^{= {1, 3, 5, 9, 15, 45}.}

Число 45 является общим делителем чисел 135 и –180 и делится на все остальные общие делители этих чисел, т. е. на 1, 3, 5, 9, 15.

Значит, (135, –180) = 45.

2. 
   Алгоритм Евклида. Из определения 1 еще не следует, что наи- больший общий делитель любого конечного множества целых чисел существует. Чтобы доказать существование наибольшего общего де- лителя, опишем способ нахождения наибольшего общего делителя, пред- ложенный великим древнегреческим математиком Евклидом. Этот спо- соб называют алгоритмом Евклида. Он основан на следующих лем- мах:
   

Лемма 1. Если a b , то (a,b)

Доказательство. Поскольку b b , то b – общий делитель аи

b. С другой стороны, если с – любой общий делитель чисел а и b, то он является делителем b. Оба условия определения 2 выполнены, и пото- му (a,b)

Лемма 2. Если а = bq + r, где a, b и r отличны от нуля, то

(a, b)=(b, r).

Доказательство, Пусть (a, b)=d; тогда a Следовательно

r Поэтому, d– общий делитель bи r. Если – общий

делитель b и r, то a Значит общий делитель а и b.

Следовательно, d , по определению н.о.д. Значит, d – н.о.д. чисел b

и r. Второе утверждение доказывается аналогично.

Алгоритм Евклида для отыскания общего наибольшего делителя чисел а и b состоит в следующем. Сначала число а делят на число b, а >

b > 0. Если a b, то по лемме 1 (a, b)=b. В противном случае получаем

остаток

r₁ : a bq₁

r₁. Делим b на

r₁.. Если b r₁, то (b, r₁)=r₁ а тогда

(a, b)= (b, r₁). Если же b не делится на

r₁ , то получится остаток

r₂ .

Делим r₁

на r₂

и т. д. Поскольку остатки, получаемые в процессе деле-

ния, убывают и являются натуральными числами, то на каком-то шагу получим деление без остатка. Последний, не равный нулю остаток явля- ется наибольшим общим делителем чисел а и b. Это утверждение можно сформулировать в виде следующей теоремы:

Теорема 2. Если

a	bq1	r1, 0	r1	b ,
b	r1q2	r2 , 0	r2	r1,
r1	r2q3	r3 , 0 …	r3	r2 ,

r_n
Доказательство. В силу леммы 2 получаем: из первой строки (a, b)= (b, r₁). из второй(b, r₁)= (r₁, r₂) и т.д. Значит (a, b)= (r_n-1, r_n).

Из равенства r_n

Поэтому (a, b)= r_n .

по лемме 1 следует r_n

и (r_n-1, r_n)=r_n.

Наибольший общий делитель более двух чисел

a₁,..., a_n

находит-

ся следующим образом: Следовательно ^(a₁^{,..., a}_n ⁾

(a₁, a₂ )

d_{n 1}.

d₁, (d₁, a₃ )

d₂ ,..., (d_{n 2} , a_n )

^dn 1 ^.

2. 
   Свойства НОД
   

Теорема 3. Наибольший по величине положительный общий делитель

целых чисел этих чисел.

a₁,..., a_n

является наибольшим общим делителем

Доказательство. Из условий теоремы вытекает, что 0 об-

щий делитель чисел

^a₁^{,..., a}_n . Поэтому <sup>d

(a</sup>₁^{,..., a}_n⁾ делится на .

Но тогда d Поскольку наибольший по величине положи-

тельный общий делитель чисел

^a₁^{,..., a}_n , a d – один из таких дели-

телей, то Из неравенств d и d следует, что d

Теорема 4. Если каждое из чисел а и b умножить на одно и то

жечислоk 0 , тоихнаибольшийобщийделительумножитсянаk.
Теорема 5. Еслиa иb то НОД чисел а и b делится наk.
Теорема 6. Если d – НОД чисел а и b, то существуют такие целые числа x и y, что ax

Доказательство. Воспользуемся алгоритмом Евклида;

a

b

^{Перепишем (1) в виде:} r₁

x₁

Аналогично перепишем (2):

r₂

(1)

(2)

где

ax₂

by₂ ,

где

и 1 – целые числа

Продолжая аналогичные рассуждения и выкладки, получим:

r_n где

x_n и y_n

целые числа. Но r_n

Значит d = ах +

+by, где х_п = х, у_п = у.

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

Пример. Найдем линейное представление наибольшего общего делителя чисел 90 и 35.

			90	35
			70	2
	35		20
	20		1
20		15
15		1
15	5
15	3
0

Применяя алгоритм Евклида к числам 90 и 35, получаем:

90	35 2	20	20 90 35 2	(1)
35	20 1	15	15 35 20 1	(2)
20	15 1	5	5 20 15 1	(3)
	15 5	3

Последний, отличный от нуля оста- ток равен 5, поэтому (90,35) = 5. Заметим, что в силу первого равенст-

ва 20 Подставляя это значе-

ние в равенство (2) 15 полу-

чаем: 15 Наконец, в равенстве

5 заменим 20 на 90 35 2, ,а 15 на 35 и получим

искомое линейное представление:

5

Здесь х = 2 и у = –5.