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

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

§ 6. Простые и составные числа

1. 
   Простые числа и их свойства.
   

Определение 1. Натуральное число р называется простым, если оно больше 1 и не имеет положительных делителей, отличных от 1 и р.

Определение 2. Натуральное число п называется составным, если оно больше 1 и имеет по крайней мере один положительный делитель, отличный от 1 и п.

Согласно определению 2, если п – составное, то существует такой

делитель , что n где 1

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

ляются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41...

Среди простых чисел имеется лишь одно четное число 2.

Итак, множество всех натуральных чисел разбивается на три под- множества: 1) простые числа, 2) составные числа, 3) число 1.

Основным результатом теории простых чисел является тот факт, что любое составное число разлагается (и притом единственным обра- зом с точностью до порядка) в произведение простых чисел. Чтобы доказать эту теорему, рассмотрим сначала некоторые свойства про- стых чисел.

Теорема 1. Если простое число р делится на некоторое натуральноечислоn то р = п..

В самом деле, если бы p то р имело бы три делителя: 1, ри

п, а следовательно, не было бы простым.

Теорема 2. Если р₁ и р₂ – различные простые числа, то р₂ не делится нар₁.

Доказательство. Так как р₂простое, то оно может делиться лишь

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

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

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

следова-

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

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

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

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

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

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

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

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

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

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

казана.

Теорема до-

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

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

Рассмотрим сначала произведение двух сомножителей. Пусть a₁a₂

Здесь возможны два случая: a₁ p или а₁ не делится на р.Если a₁

то утверждение доказано. Если а₁ не делится на р, то согласно тео- реме 4 §3 а₁ и р взаимно просты; тогда на основании теоремы 7 §3 a₂