Теорема 2. Наименьший отличный от единицы делитель составного числа a(простой по теореме 1) не превосходит √a.

Доказательство: пусть q – это делитель a= q*a₁, a₁ ≥ q, откуда, перемножая и сокращая на a₁, получим a ≥ q², q ≤ √a.

Эта теорема дает критерий, позволяющий судить, является ли натуральное число a простым или составным.

Последовательность простых чисел неограниченна. Этот результат был получен еще Евклидом и помещен в 9 веке в книге его “Начал” в качестве 20-ой теории.

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

Доказательство: предполагается, что множество простых чисел конечно и состоит из чисел 2, 3,..., p_r(*), где p_r – последнее самое большое простое число.

Рассмотрим N= 2*3... p_r+1, N > 1 N- либо простое, либо составное

а) если N- простое; N > p_i, где p_i т.е. > любого простого числа

(т.к. других простых не существует) N- не может быть простым;

б) если N-составное; N 2, N 3,..., N p не ни на одно простое число, т.е. не имеет делителей, отличных от 1 и N не составное.

N 1, ни простое, ни составное – противоречие. ▲

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

Литература: 1, с.15-20; 2, с.3-8

Контрольные вопросы:

1. Сформулируйте теорему о делении с остатком.

2. Дайте 2 формулировки теоремы Безу.

3. Что называется НОД двух чисел?

4. Перечислите свойства НОД.

5. В чём состоит алгоритм Евклида, как он применяется при нахождении НОД двух чисел?

6. Что называется НОК двух чисел?

7. Какие числа называются простыми, составными?

8. Какая формула связывает НОК и НОД двух чисел?

9. Конечно ли множество простых чисел?