Интуиция на простые числа

[lel0lel]

Не так давно была тема "физическая интуиция" http://dxdy.ru/topic119622.html. Можно сказать, что эта тема создана по мотивам.

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

[ИСН]

Это не интуиция, это простенький расчёт. В первом надо проверять делимость на 7 через 1001, во втором - тоже на 7, только не у самого числа, а у показателя степени, в остальных - на 3.

[yk2ru]

В третьем примере как помогает проверка делимости на 3?

[ИСН]

Никак. Зато помогает в четвёртом, что оставляет единственный вариант.

[kotenok gav]

А я думал второй...

[lel0lel]

Рассуждения, приводящие к верному ответу, расписал ИСН.

kotenok gav в сообщении #1242581 писал(а):

А я думал второй...

Во втором, как мне казалось, сразу бросается в глаза, что $91=7\cdot 13$. Поэтому число $2^{91}-1$ делится на $2^7-1$, а также на $2^{13}-1$. На этом базируется известный факт, что простые числа Мерсенна должны иметь простой показатель.

Простые из пункта 3 были найдены при тестировании алгоритма быстрого вычисления линейных рекуррентных последовательностей 2-го порядка в детерминированном тесте простоты. Немного был удивлён, что в OEIS они отсутствуют, хотя размеры чисел, по современным меркам, весьма скромные и найти их можно меньше чем за сутки. Вероятно, это связано с отсутствием интереса к простым вида $4\cdot 11^p-1$.