# number theory -prove there is a solution to $x^5\equiv k \pmod{p}$

$p$ is a prime such that $p-1$ is not divisible by $5$.

$k$ is an integer number.

Prove there is a solution to $x^5 \equiv k \pmod{p}$.

I try to post another question but it's tell me: This post does not meet our quality standards.

Why?

P is an odd prime. Now by Euler-Fermat:

$x^2=1(mod3)$

$x^{(p-1)}=1(modp)$

Show there is $k<2(p-1)$ such that $x^k=1(mod3p)$ .

Thanks.

-
I took the liberty to correct your divided to divisible, and to do some $\LaTeX$ formatting. –  Andreas Caranti Mar 27 '13 at 11:44
Someone can help me with "This post does not meet our quality standards."? I did my best...what is the problem? –  user1932595 Mar 27 '13 at 13:09

If $5$ does not divide $p-1$, then $\gcd(5, p-1) = 1$. Bézout tells you there are $a, b \in \Bbb{Z}$ such that $5 a + (p-1) b = 1$.

Now by Euler-Fermat $5^{p-1} \equiv 1 \pmod{p}$. It follows that

$$k = k^{1} = k^{a \cdot 5 + (p-1) \cdot b} \equiv (k^{a})^{5} \pmod{p},$$ so $x = k^{a}$ is your solution.

-
thank you! In the question there is a clue: use primitive root mod p. Can you think on another sulotion ehich use this clue? –  user1932595 Mar 27 '13 at 12:07
@user1932595, so you have to use a primitive root. Let $z$ be a primitive root modulo $p$. Since $\gcd(5, p-1) = 1$, we have that also $z^{5}$ is also a primitive root. Therefore there is an $e$ such that $k = (z^{5})^{e} = (z^{e})^{5}$. –  Andreas Caranti Mar 27 '13 at 12:17
I don't understand why z^5 is also a primitive root.. –  user1932595 Mar 27 '13 at 12:35
@user1932595, a primitive root is (by a definition you should have been exposed to) just an element of order $p-1$. Now you should know that if an element $z$ has order $n$, then its power $z^{t}$ has order $n / \gcd(n, t)$. –  Andreas Caranti Mar 27 '13 at 12:44
right, I forgot from this...and the conclusion is from the fact that (z^5)i are diffrent modolu p. right? –  user1932595 Mar 27 '13 at 12:49

Another approach, not using the hint:
Since $U_p^*=(\mathbb Z/p\mathbb Z)^*$ is of order =$p-1$, and as $\gcd(5,p-1)=1$, we know that there is no element of order =$5$. hence there is only one trivial solution to $x^5=1$ in $U_p^*$, i.e. $x=1$. So the homomorphism $x\to x^5$ has trivial kernel, i.e. it is a monomorphism. Since $U_p^*$ is a finite set, it is also an epimorphism as well. So, for any $k$, there is some $x$ such that $x^5=k$, as required to be shown.

P.S. The notation is not standard, but adapted just for the sake of convenience.
Barring mistakes, and regards then.

-
You surely mean to say that $x = 1$ is the only solution to $x^{5} = 1$. –  Andreas Caranti Mar 27 '13 at 12:45
@AndreasCaranti Thanks for pointing it out! I wonder what I was thinking at that moment... –  awllower Mar 27 '13 at 12:47
OK, don't worry, it's quite normal to automatically ignore the trivial solution(s). –  Andreas Caranti Mar 27 '13 at 13:27
@AndreasCaranti Thanks for the understanding. :D –  awllower Mar 27 '13 at 19:42

It is case $\rm\:(k,n) = (5,p\!-\!1) = 1\:$ of the Easy k'th Power Criterion that I mentioned recently.

Suppose $\rm\, g^n = 1.\,$ Then exponents on $\rm\,g\,$ can be interpreted $\rm\ mod\ n\!:\ i \equiv m\:$ $\Rightarrow$ $\rm\,g^i = g^{m}.\$ So it is clear that $\rm\,g^i\,$ is a $\rm\,k$'th power if $\rm\ mod\ n\!:\, k\mid i,\$ i.e. $\rm\ i\equiv jk,\,$ so $\rm\,g^i = g^{jk} = (g^j)^k.\,$ By $\rm\color{#C00}{Bezout}$

$$\rm k\,|\, i\ \ (mod\ n)\!\iff\! \exists\,j\!:\ jk\equiv i\:\ (mod\ n)\!\iff\! \exists\, j,m\!:\ jk \!+\! mn = i\color{#C00}{\!\iff\!} (k,n)\,|\, i$$

Hence we have conceptually derived a proof of the following

Theorem $\rm\ \ \ g^n = 1,\,\ (k,n)\mid i\:\Rightarrow\: g^i\,$ is a $\rm\,k$'th power $\ \$ [Easy $\rm\,k$'th Power Criterion]

Proof $\rm\ \ By\ Bezout,\,\ (k,n)\mid i\:\Rightarrow\:k\mid i\ \ (mod\ n)\: \Rightarrow\:i\equiv jk\ \ (mod\ n)\:\Rightarrow\: g^i = g^{jk} = (g^j)^k$

Note $\,\$ That $\rm\ \ k\,|\, i\:\ (mod\ n)\!\iff\! (k,n)\,|\: i\ \,$ frequently proves conceptually handy,  e.g.  see here. $\$ The reason behind this will become clearer when one studies cyclic groups and (principal) ideals.

-