общий простой делитель 2^n-3 и 3^n-2

[maxal]

Известно, что для $n=59868530942221$ числа $2^n-3$ и $3^n-2$ имеют общий простой делитель. Найдите его.

[Null]

$p-1|n^2-1$?

[maxal]

Null, и чему же равно $p$?

[dmd]

Решение Null: 92009554676141

[gris]

А я вчера принял последнюю цифру $n$ за семёрку. И так обрадовался, что накатал ответ — $5$. А потом призадумался, а чего это maxal такую задачку дал. И увидел, что там не так всё просто А жаль.

[maxal]

dmd в сообщении #1281173 писал(а):

Решение Null: 92009554676141

Оно. Кстати, такие простые довольно редки - см. A196627 и A196628.

Null в сообщении #1281083 писал(а):

$p-1|n^2-1$?

Вообще говоря, это делимость не обязана выполнятся, но в этой задаче нам "повезло". Однако, даже найдя единственное $p$ таким образом, мы не можем утверждать, что $\gcd(2^n-3,3^n-2)=p$.

Степень везения предлагаю оценить следующей задачкой:
Пусть $a$ и $b$ случайные ненулевые вычеты по модулю простого $p$. Понятно, что мультипликативные порядки $\mathrm{ord}_p(a)$ и $\mathrm{ord}_p(b)$ являются делителями $p-1$, а вот какова вероятность того, что $\mathrm{lcm}(\mathrm{ord}_p(a),\mathrm{ord}_p(b))=p-1$ ?

(Если это равенство выполняется для искомого $p$ и $(a,b)=(2,3)$ в исходной задаче, то в виду делимости $\mathrm{lcm}(\mathrm{ord}_p(a),\mathrm{ord}_p(b)) \mid (n^2-1)$, мы как раз и получим $(p-1)\mid (n^2-1)$.)