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

натурального числа n k

S_{k 1} 1 3 5 ... (2k

1, т. е. что

1) (2k

1. 
   (k
   

1)².

В самом деле, _{Sk 1}

S_k (2k 1)

k ² (2k

1. 
   (k
   

1)² .

На основании принципа математической индукции отсюда вы- текает справедливость утверждения для всех значений п.

Иногда нужно доказать справедливость некоторого утверждения не

для всех натуральных чисел, а лишь для n где p фиксированное

натуральное число. В этом случае принцип математической индукции формулируется следующим образом:

Если утверждение справедливо при n p и если из справедливости

утверждения для n

где k

следует его справедливость для

n то утверждение верно для всех n

Заметим, что и в данном случае при проведении индукционного ша-

га нельзя использовать никакие конкретные свойства числа k ,

свойства k

кроме

§ 2. Делимость

1. 
   Отношение делимости и его свойства. В школьном курсе матема- тики читатель ознакомился с натуральными и целыми числами. Обозна- чим множество натуральных чисел через N:
   

N ={1, 2, …},

а множество целых чисел – через Z:

Z= {... , – 3, – 2, – 1, 0, 1, 2, 3, …}.

Будем считать известными свойства операций над целыми, числами (сложения, вычитания, умножения), понятие модуля целого числа и свойства этого понятия.

Определение 1. Целое число а делится на целое число b

существует такое целое число с, что a b c .

0 , если

Число а называется делимым, b – делителем и с – частным.

Если а делится на b, то пишут (а кратно b).

Обратным к отношению рое обозначают так: b/а.

Отношение делимости

является отношение «b делит а», кото-
является бинарным отношением в .

Оно обладает следующими свойствами:

1. 
   Отношение делимости рефлексивно, т. е. для любого
   

a имеем a a . Это следует из того, что a и 1

2. 
   Отношение делимости транзитивно, т. е. из и b
   

следует Действительно, так как a b и b c , то существуют такие

целые числа q и t, что a b q и b Но тогда

a b q

(c t) q c

(t q). Так как произведение целых чисел – це-

лое число, то tq , и потому a c.

3. 
   Если a b , то (
   

1. 
   b , и (
   

а) (

2. 
   , т.е. отношение делимо-
   

сти сохраняется при изменении знаков делимого и делителя.

В самом деле, если a b , то a bq , где q а тогда

a b(

q), a

( b)(

q),

a ( b) q.

4. 
   Если a c и b c , то a b c.
   

В самом деле, так как a c и b c то существуют такие целые чис-

ла q и t, что а = cq и b = ct. Но тогда

1. b cq ct c(q t).

Т.к.

q t целое число, то a b делится на с.

Точно так же доказывается, что из a c , b c следует (a b) c.

5. 
   Если a c и b , то ^{(ab) c.}
   

В самом деле, так как a c , то существуют такое целое число q, что

а = cq. Но тогда ab

(cq)

2. 
   c(qt) . Так как qb , то (ab) c.
   

Отметим, что утверждения, обратные 4) и 5), ложны: из дели- мости суммы не вытекает делимость слагаемых, а из делимости произ- ведения не вытекает делимость сомножителей.

6. 
   ^Если (a b) c ^{и a c , то b c .}
   
7. 
   Если a c , a b не делится на с, то а ± b не делится на с.
   

11. 
    Если
    

^и b a ^{, то a и a}

Деление с остатком.

Разделить целое число а на целое число

b с остатком – это

значит найти два таких целых числа q и r , чтобы выполнялись усло- вия:

1) а = bq + r, 2) 0

Число q называется неполным частным, а r – остатком.

Теорема 1. Каковы бы ни были целое число а и целое число b 0 ,

всегда возможно, и притом единственным способом, разделить а на b с остатком.

Докажем сначала возможность деления с остатком. Рассмотрим все случаи, которые здесь могут представиться.

1. 
   а – любое целое число, b > 0.
   

Рассмотрим множество всех чисел, кратных b, и расположим его в порядке возрастания: ...( 2)b,( 1)b, 0,b, 2b,...

Пусть bq – наибольшее кратное числа b, не превышающее а. Тогда

a но a

т. е. bq

, откуда 0

Положив а – bq = r, получим:

a

2. 
   а – целое число, b < 0.
   

Так как b < 0, то –b > 0 и согласно случаю 1) деление а на –b воз- можно, а это означает существование таких целых чисел q и r, что

a или a

Возможность деления с остатком доказана.

Теперь докажем единственность деления с остатком.

Пусть деление а на b не единственно, т. е. пусть существуют два не-

полных частных q₁ и q₂ и два остатка r₁ и r₂ такие, что:

a bq₁

a bq₂

r₁, 0 r₁ b ,

r₂ , 0 r₂ b ,

Тогда Так как

bq₁

0

или b(q₁

и 0
то r₂

(*)

Но в этом случае равенство (*) возможно лишь при условии:

r₂ r₁ 0 , или r₂

но тогда q₁

q₂ 0 , или q₁

Единствен-

ность доказана.

^{Пример1. Доказать, что} (n⁴
6n³
11n²
6n) 24.

^{Разложим многочлен} n⁴

6n³

11n²

6n ^{на множители. Имеем:}

n⁴ 6n³

11n²

6n n(n

1)(n

2)(n

3).

Но из четырех последовательных натуральных чисел два числа чет- ные, причем одно делится на 4, следовательно, их произведение делится на 8. Кроме того, из трех последовательных натуральных чисел

n,(n

n(n

1),(n

1)(n

2)

2)(n

^{одно обязательно делится на 3.} (8,3) 1. ^{Таким образом,}

3) 24.

§ 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, а >

остаток

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

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 Наконец, в равенстве