Критерий решения сравнения [Теория чисел]

[Whitaker]

Здравствуйте!

Пусть $p$ - простое число и $n>1$ -- делитель $p-1$ и $(A,p)=1$. Доказать, что сравнение $x^n\equiv A\pmod p$ разрешимо тогда и только тогда, когда $A^\frac{p-1}{n}\equiv 1\pmod p$.

Необходимость я доказал. Пусть сравнение разрешимо. Тогда $x_0^n\equiv A\pmod p$ и возводим это в степень $\frac{p-1}{n}$ и нетрудно показать, что $(x_0,p)=1$ и пользуясь малой теоремой Ферма получаем, что $A^\frac{p-1}{n}\equiv 1\pmod p$
А вот как доказать достаточность я что-то не могу. Как использовать условие $A^\frac{p-1}{n}\equiv 1\pmod p$ я не знаю.

Может подскажете полезную идею?

С уважением, Whitaker.

[AV_77]

Мультипликативная группа кольца $\mathbb{Z}_p$ циклическая.

[Whitaker]

AV_77
Это да! Такие мысли также были у меня, но не могу понять как это использовать со сравнением $A^{\frac{p-1}{n}}\equiv 1\pmod p$

[AV_77]

Пусть $\alpha$ - образующий. Тогда $A = \alpha^k$, причем из $A^{\frac{p-1}{n}} = 1$ следует, что $\alpha^{k \frac{p-1}{n}} = 1$.

[Whitaker]

Ну да. А что это дает?

[AV_77]

Как что? При этом $k \frac{p-1}{n} = s(p-1)$, откуда $k = sn$, то есть $k$ делится на $n$. Осталось в явном виде указать нужную степень порождающего элемента.

[Whitaker]

AV_77
Спасибо Вам! Теперь понятно. Что-то сам не допер до этого