Числа Ферма. Теорема Пепина.

Теорема.

Если число вида p=aⁿ+1 – простое, то 1) a – четное;

2) n=2^k для некоторого k.

Доказательство:

Четность a очевидна, так как иначе p было бы четным, а значит не простым.

Предположим теперь m>2 - нечетное число : n= m·2^k. Тогда

=a^n—m—a^n—2m+…+a^3m—a^2m+a^m—a⁰ Z.

Тогда (a^m+1)\(aⁿ+1), значит p – составное число. Предположение неверно, следовательно верно обратное.

□

Числа F_k= +1 называются числами Ферма.

F₀=3, F₁=5, F₂=17, F₃=257, F₄=65739 – простые числа. Пьер Ферма выдвигал гипотезу о простоте всех чисел Ферма, но Леонардом Эйлером в 1732 г. была показана составность числа F₅.

В настоящее время существует следующий критерий проверки чисел Ферма на простоту:

Теорема Пепина

F_k – простое число .

Доказательство:

Пусть F_k – простое число. Тогда по критерию Эйлера для символа Лежандра,

.

В силу простоты, F_k не делится на 3.

Поэтому возможны два случая: F_kmod 3=1 или F_k mod 3=2.

Случай F_k mod 3=1 невозможен, так как это значило бы, что mod 3 = 0, а это не так. Поэтому F_k mod 3=2, и тогда

□

На основании теоремы Пепина построен тест Пепина, проверяющий верность сравнения . Тест Пепина детерминированный, состоит из одной итерации и дает точный ответ о простоте или составности числа Ферма.

Числа Мерсенна.

Теорема 1

Если число вида p=aⁿ—1 – простое 1) a – четное;

2) n – простое.

Доказательство:

Четность а очевидна, так как иначе р было бы четным, а значит, составным.

Допустим, что n – не простое n=mk. Тогда

=a^k(m—1)+a^k(m—2)+…+a^k+1 Z.

Тогда (a^k—1)\(aⁿ—1), значит р – не простое число. Предположение неверно, значит верно обратное.

□

Простые числа вида M_p=2^p—1, где р – простое число, называются числами Мерсенна.

Теорема 2

Число вида M_p=2^p—1, где р>2 – простое число, является простым в последовательности, определенной равенствами u₀=4, u_i+1=(u_i²—2) mod M_p, выполняется u_p—2≡0(mod M_p).

■

Из Теорем 1 и 2 следует