Возведение в степень по модулю простого

[dmd]

Пусть для простого $p$ и натуральных $a<p,x$ выполняется

$x^x\equiv a\pmod{p}$.

1) Для $p<1000$ найдите все пары $(p,n)$, где $n$ натуральное, для которых

$x=a^a+j\cdot n$,

где $a^a<n$ и $j=$0,1,2,3,....

2) Для аналогичных $j,n$ и $p>1000$ найдите первую пару $(p,n)$, для которой $a=7$.

[Null]

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

$j=$0,1,2,3,....

Существует $j$ или для любого $j$?

[dmd]

Null
Для любого положительного целого $j$ от нуля до бесконечности.

[kotenok gav]

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

положительного <...> от нуля

???

[Dendr]

$(2, 2), (p,2p)$ - годится?
Во всяком случае, как часть ответа?

[dmd]

Ок. Предлагаю тривиальные случаи $p=2$ и $a=1$ не рассматривать.

Т.е. условие тогда начинается так: "Пусть для простого $p>2$ и натуральных $1<a<p,x$ выполняется..."


Подсказка. Простое $127$ образует две пары $(p,n)$=(127,889),(127,5334).

Примеры (на pari/gp; в Вольфраме есть PowerMod; наверное, в любых CAS есть возведение в степень по модулю):

? j=0;a=2;x=a^a+j*889;Mod(x,127)^x
%1 = Mod(2, 127)
?
? j=777;a=2;x=a^a+j*889;Mod(x,127)^x
%2 = Mod(2, 127)
?
? j=787878;a=2;x=a^a+j*889;Mod(x,127)^x
%3 = Mod(2, 127)
?
?
? j=0;a=5;x=a^a+j*5334;Mod(x,127)^x
%4 = Mod(5, 127)
?
? j=888;a=5;x=a^a+j*5334;Mod(x,127)^x
%5 = Mod(5, 127)
?
? j=898989;a=5;x=a^a+j*5334;Mod(x,127)^x
%6 = Mod(5, 127)

[vorvalm]

Элементарное решение получим при

$a = p - 1,\;\;x=\frac{p-1} 2=\frac a 2.$

если $x$ квадратичный вычет по модулю $p$

[Null]

Условие задачи непонятно.