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

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

 Простое число – натуральное число, которое имеет только два разных натуральных делителя: 1 и само себя. 

 Составное число – число, которое имеет более двух натуральных делителей. 

 Рассмотрим несколько теорем о простых числах: 

1. Множество простых чисел бесконечно.

2. Если одно простое число делится нацело на другое, то они равны.

3. Для любого натурального числа и простого числа справедливо одно из двух утверждений: или натуральное число делится нацело на простое, или их НОД равен 1.

4. Если xy ⋮ m, где x ∈ N, y ∈ N, m – простое число, то x ⋮ m или y ⋮ m.

Следствие из теоремы (4): если произведение x₁x₂ …..x_n натуральных чисел делится нацело на простое число m, то хотя бы один из множителей x₁, x₂,_…, x_n делится нацело на m.

5. Любое натуральное число, отличное от 1, или является простым, или может быть представлено в виде произведения простых чисел.

6. Малая теорема Ферма: если натуральное число x не делится нацело на простое число m, то x^m-1 ≡ 1 (mod n).

Следствие из теоремы (5): для любого натурального числа x и простого числа m справедливо сравнение x^m ≡ x (mod m).

 Рассмотрим несколько примеров 

 Пример 1:  Натуральное число x не делится нацело на 23. Докажите, что одно из чисел x¹¹ – 1 или x¹¹ + 1 делится нацело на 23.

 Попробуйте решить эту задачу самостоятельно, а если не получается, то просто нажмите на это предложение. Решение:Сократим с помощью формул сокращённого умножения: (x^11 - 1)(x^11 + 1) = x^22 - 1. Из следствия малой теоремы Ферма: x^23 ≡ x (mod 23), x^23 - x ≡ 0 (mod 23), x(x^22 - 1) ≡ 0 (mod 23), x(x^11 - 1)(x^11 + 1) ≡ 0(mod 23), x^11 - 1 ≡ 0 (mod 23) или x^14 + 1 ≡ 0 (mod 23), (x^11 - 1) ⋮ 23 или (x^11 + 1) ⋮ 23.

 Пример 2:  Найдите остаток от деления числа 5¹⁰⁴ на 103.

 Попробуйте решить эту задачу самостоятельно, а если не получается, то просто нажмите на это предложение. Решение:103 - простое число, по малой теореме Ферма 5^102 ≡ 1 (mod 103), 5^104 ≡ 25 (mod 103).