2
$\begingroup$

Can someone please help me prove the following statement:

If a prime number $p$ satisfies $\gcd(a,p−1) = 1$, then for every integer $b$ the congruence relation $x^a \equiv b \pmod{p}$ has a solution.

$\endgroup$
2
$\begingroup$

Using Discrete Logarithm wrt primitive root $g\pmod p$

$\displaystyle a\cdot$ind$_gx\equiv$ind$_gb\pmod{p-1}$

Using Linear congruence theorem (Proof), as $\displaystyle d=(a,p-1)=1$ always divides ind$_gb,$ the number of solutions will be $d$

$\endgroup$
1
  • $\begingroup$ It is not without interest to note that there are cases in which $a|{p-1}$ and $x^a=b$ could have solution for all $b$ excepting $b=0$. $\endgroup$
    – Piquito
    Oct 23 '17 at 0:27
0
$\begingroup$

The set $S=\{1^a,2^a,\cdots,(p-1)^a,p^a\}$ is contained in $\mathbb F_p$ and can be equal or distinct of it. If $(a,p-1)=1$ then for $b=0$ in $\mathbb F_p$ we have $p^a=0$ and $x^a=0$ has a solution. Let $b\ne0$. If $x^a=b$ has no solution, then $x^a=y^a$ for some distinct elements of the group multiplicative $\mathbb F_p^*$ then $z^a=1$ where $z=x\cdot y^{-1}$. But this implies $a$ divides $p-1$ by FLT, contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.