# Number Theory: Prove $x^k\equiv a\pmod{p}$ is solvable for $r^d,r^{2d},\dots,r^{[(p-1)/d]d}$.

I think I have the proof to this problem, but I'm not sure if it's correct:

Let $r$ be a primitive root of the odd prime $p$, and let $d=\gcd(k,p-1)$. Prove that the values of $a$ for which the congruence $x^k\equiv a\pmod{p}$ is solvable are $r^d,r^{2d},r^{3d},\dots,r^{[(p-1)/d]d}$.

I also use this theorem in my proof:

Theorem 8.12 Corollary

Let $p$ be a prime and $\gcd(a,p)=1$. Then the congruence $x^k\equiv a\pmod{p}$ has a solution if and only if $a^{(p-1)/d}\equiv 1\pmod{p}$, where $d=\gcd(k,p-1)$.

Proof:

By Theorem 8.12 Corollary, $x^k\equiv a\pmod{p}$ has a solution $\iff$ $a^{(p-1)/d}\equiv 1\pmod{p}$.

Consider $a=r^{td}$, some $t\in\mathbb{Z}, 0<t\leq(p-1)/d$.

Then, $(r^{td})^{(p-1)/d}=r^{t(p-1)}=(r^{p-1})^t\equiv 1^t\equiv 1\pmod{p}$, by Fermat's Little Theorem.

Note also that for some $(p-1)/d<s\in\mathbb{Z}$, $r^{sd}\equiv r^{td}$ for some $0<t\leq(p-1)/d$ since $r^{sd}=r^{[t+(p-1)/d]d}=r^{td}r^{p-1}\equiv r^{td}\cdot 1\equiv r^{td}\pmod{p}$ by Fermat's Little Theorem.

Thus, the values of $a$ for which $x^k\equiv a\pmod{p}$ is solvable are $r^d,r^{2d},r^{3d},\dots,r^{[(p-1)/d]d}$. $\blacksquare$

Still, I'm not sure how to prove that there are no other $a$'s for which the congruence is solvable...

• In the end, how many solutions do you have, $(p-1)/d$? Could they be more than $k$? Or maybe I got confused with your notation... P.S. just for curiosity, the theorem you cite from which book comes from? – PITTALUGA Nov 19 '15 at 12:29
• Oh I see what you mean, to count how many solutions there are. That makes sense. Thank you very much! (The book I use is called Elementary Number Theory by Burton.) – MathQuestion Nov 19 '15 at 19:09
• How can you say s for s> (p-1)/d that it is t + (p-1)/d ? I don't get that part . – Randin Jan 31 '18 at 10:40