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

на 1 и на р₂. По условию p₁

тельно, р₂ не делится на р₁.

а по определению p₁

следова-

Теорема 3. Всякое натуральное число п > 1 делится хотя бы на одно простое число.

Доказательство. Применим метод математической индукции.

1. 
   Для натурального числа п = 2 теорема справедлива, т. е. 2 делится на простое число 2.
   
2. 
   Предположим, что утверждение теоремы справедливо для всех натуральных чисел, больших 1 и меньших п, и докажем спра- ведливость теоремы для числа п.
   

Если п простое, то п делится на простое число р = п, и теорема доказана.

Если же п составное, то ⁿ

Так как п₁ < п, то по индуктивному предположению для п₁ теоре- ма верна, т. е. п₁ делится хотя бы на одно простое число р. Но тогда и п делится на р. Теорема доказана.

Теорема 4. Если п – натуральное число, а р – простое число, то либо п делится на р, либо п и р взаимно просты.

Доказательство. Пусть d – наибольший общий делитель чисел п и

р, т. е. (п, р) = d. Так как р – простое число, то либо d = 1, либо d = р.

Если d = 1, то п и р взаимно просты. Если d = р, то n

казана.

Теорема до-

ший простой делитель, то n

причем p

Умножая левую

и правую части последнего неравенства на равные числа рп₁ и п, полу-

чим

^{p2n n n,} откуда p²

или p

1 1
Из теоремы 6 следует, что если число п не делится ни на одно про-

стое число, не превосходящее

п – составное.

, то п – простое; в противном случае

Теорема 7 (основная теорема арифметики). Всякое натуральное число п>1 либо просто, либо может быть представлено, и притом единственным образом, в виде произведения простых чисел.

Два представления, отличающиеся только порядком расположе- ния сомножителей, будем считать совпадающими.

Существование разложения. Пусть п = 2. Так как 2 – простое чис- ло, то для п = 2 утверждение доказано.

Предположим, что утверждение справедливо для всех натураль- ных чисел, больших или равных 2, но меньших п, и докажем спра- ведливость его для числа п.

Рассмотрим натуральное число п. Если п – простое, то утверж- дение доказано. Если п – составное, то его можно представить в ви- де:

^{n n}₁ⁿ₂ ^, где ¹
Для чисел п₁ и п₂ согласно индуктивному предположению ут- верждение справедливо:

Тогда
p₁ p₂... p_k
q₁q₂ ...q_s .
(3)

Левая часть равенства (3) делится на простое число p₁. Следова- тельно, и правая часть тоже делится на p₁. Согласно теореме 5 п. I хо-

тя бы один из сомножителей произведения

q₁q₂...q_s должен делиться

на p₁. Пусть q₁

Так как q₁ – простое число и p₁ > 1, то по теореме 1

п. 1 q₁ p₁. .

Разделив обе части равенства (3) на p₁, получим:

p₂... p_k

(3)

Так как

p₂... p_k è q₂...q_s

меньше, чем п, то по индуктивному пред-

положению из равенства (3) следует, что ^k

Таким образом,

p₁

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

Итак, согласно основной теореме арифметики всякое составное чис- ло п>1 может быть представлено в виде произведения простых чисел. Среди этих простых множителей могут встречаться одинаковые. Пусть,

например, p₁ встречается

раз, р₂ –

раз, ... ,

^p_{k k} раз; тогда

Множители

p₁ p₂ ... p_k обычно располагают в порядке возрастания.

Представление натурального числа п в форме (4) называется канони- ческим; это представление единственно. Представление (4) называют также факторизацией числа п.

Пример. 1172

Следствие 1. Наибольший общий делитель чисел a и b имеет вид:

d где

a

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

k где

a

3. 
   Бесконечность множества простых чисел.
   

Теорема 8 (Евклида). Множество простых чисел бесконечно.

Д о к а з а т е л ь с т в о (от противного). Предположим, что мно-

жество простых чисел конечно: пусть это будут числа p₁ 2, p₂ ,..., p_k

где

p_k – наибольшее простое число.

Составим произведение p₁

смотрим натуральное число n

p₂ ...

p_k всех простых чисел и рас-

Так как n p_k , то

п должно быть составным. Следовательно, оно должно делиться на некоторое простое число. Но по предположению все простые числа

принадлежат конечному множеству ^{{ p}₁^{, p}₂ ^{,..., p}_k ^}.

Значит, п делит-

ся на одно из чисел

p₁, p₂ ,..., p_k

скажем, на р₁. Поскольку произведе-

ние

p₁ p₂ ... p_k тоже делится на р₁ и n p₁

p₂ ... p_k

1 , то и число 1

должно делиться, на р₁. Но это невозможно, так как 1< р₁. Получен- ное противоречие доказывает теорему.