Где-то на Википедии видел такую фразу: чтобы [math]2^p - 1[/math] было простым, должно быть простым и [math]p[/math], потому что если [math]p = x y[/math], то [math]2^p - 1[/math] делится на [math]2^x - 1[/math] и на [math]2^y - 1[/math]. Как это выводится? Подстановками вижу что работает, но что-то не понимаю как это доказать. Wolfram Alpha тоже не понимает как разложить эту дробь. PS. Как записать [math]2^{xy}[/math] в этом вашем math? PSS _DEN_, вероятно, вот так [МАТН]2^{xy}[/МАТН]
ну хз, критерий Поклингтона. Если совсем упарываться, то да, числа Софи-Жермен тупо ищуться перебором.
Больше похоже на числа Мерсенна. https://www.pvsm.ru/programmirovanie/253678 Для таких чисел есть куча всяких тестов на простоту, вероятностные и детерминированные. Даже такая хрень есть https://ru.wikipedia.org/wiki/Тест_Агравала_—_Каяла_—_Саксены
Числа Мерсенна, да. Но вопрос был не в этом. Фраза на вики как бы намекала, что сабж можно успростить таким образом, что будет видно, что результат деления - целый. То есть, при делении в буквенном виде должно получиться выражение, из которого видно, что результат деления - целый. Или я чего-то не понимаю?
[math](2^x - 1)\cdot (2^x - 1) = 2^{2x} - 2^x - 2^x + 1 = 2^{2x} - 2(2^x - 1) - 1[/math] т.к. [math]1=2-1[/math] [math](2^{nx} -1) \cdot(2^x - 1) = 2^{(n+1)x} - 2^{nx} - 2^x +1 =[/math] [math]= 2^{(n+1)x} - (2^{nx} - 1) - (2^x - 1) - 1[/math] : [math]n=2,3,....[/math] основание не обязательно 2 для этого
_DEN_, Врядле это можно свернуть. Линейная обратная зависимость двух не линейных функций, которые матем врядле решаются.
