Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

share|improve this question
1  
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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