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

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

Разложение составных чисел на простые множители.

Теорема 6. Если натуральное число п составное, а р – наименьший его простой делитель, то p

Доказательство. Так как п – составное число, а р – его наимень-

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

причем p

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

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

чим

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

или p

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

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

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

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

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

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

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

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

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

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

n₁

Тогда

n

Существование разложения доказано.

Единственность разложения. Пусть п = 2. Число 2 простое, и его нельзя представить в виде произведения простых чисел.

Итак, для п = 2 утверждение справедливо.

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

n p₁ p₂...p_k,

Тогда
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} раз; тогда

разложение числа п на простые множители можно записать следую- щим образом:

n (4)

Множители

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< р₁. Получен- ное противоречие доказывает теорему.

Таким образом, простых чисел бесконечно много. Вместе с тем ока- зывается, что простые числа составляют лишь небольшую часть чисел натурального ряда.