Вопрос школьника
Пусть р — простое число. Укажите наименьшее значение р, при котором значение выражения 2р — 1 не является простым числом.
Ответ от учителя
Для решения этой задачи можно использовать теорему Эйлера, которая гласит, что если a и n взаимно просты, то a^φ(n) ≡ 1 (mod n), где φ(n) — функция Эйлера, равная количеству чисел от 1 до n, взаимно простых с n.
В данном случае мы имеем выражение 2р — 1, которое не является простым числом. Значит, оно должно иметь делитель, отличный от 1 и самого себя. Пусть этот делитель равен d.
Тогда 2р — 1 ≡ 0 (mod d), то есть 2р ≡ 1 (mod d).
Заметим, что 2 и р взаимно просты, поэтому по теореме Эйлера имеем 2^φ(d) ≡ 1 (mod d).
Так как 2р ≡ 1 (mod d), то 2^2р ≡ 1 (mod d).
Значит, 2^НОД(2р, φ(d)) ≡ 1 (mod d).
НОД(2р, φ(d)) может быть равен либо 1, либо 2.
Если НОД(2р, φ(d)) = 1, то 2^1 ≡ 1 (mod d), то есть d делит 2 — 1 = 1, что невозможно.
Если НОД(2р, φ(d)) = 2, то 2^2 ≡ 1 (mod d), то есть d делит 3.
Значит, наименьшее значение р, при котором 2р — 1 не является простым числом, равно 3.
Проверим: 2*3 — 1 = 5, что является простым числом. Но если р = 3, то 2р — 1 = 2*3 — 1 = 5, что уже не является простым числом.
