Задача интересная, хочу решить ее сам, но не могу сообразить как это сделать
Из условия можно вывести 5^{2p^2}-1\ \vdots \ p, при этом 5^{p-1}-1\ \vdots\ p
Теперь нужно использовать факт (докажи) (a^m-1, a^n-1)=a^{(m,n)}-1
4 лайка
Не удобно просить, но можете расписать пожалуйста
Доказательство факта
По алгоритму Евклида (m>n)
(a^m - 1, a^n - 1) = (a^m - a^n, a^n - 1) = (a^n(a^{m-n} - 1), a^n - 1) = (a^{m-n} - 1, a^n - 1) = \ldots
То есть (m, n) \to (m - n, n), далее если m - n \geq n
(m,n) \to (m - n, n) \to (m-2n, n), продолжая таким же образом фактически исполняем тот же алгоритм Евклида, но для степеней. Как несложно понять он приведет к \gcd(m, n)
Про задачу
p \mid 5^{2p^2} - 1
p \mid 5^{p-1} - 1
Тогда p \mid d = gcd(5^{2p^2} - 1, 5^{p-1} - 1) = 5^{(2p^2, p-1)} - 1 \implies p \mid 5^{(2p^2, p-1)} - 1 = 5^2 - 1 , пойми почему (2p^2, p-1) = 2 при p > 3 \implies p \mid 5^2 - 1 = 24 = 8 \cdot 3 \implies p = 3
случай где p=2, рассмотреть надо отдельно
7 лайков