6
$\begingroup$

Let $\gcd(a,p)=1$ where $p$ is prime, and let $n>0$. Prove that the congruence equation $x^n=a \pmod p$ has a solution if and only if $ordp(a)|\frac{(p-1)}{\gcd(n,p-1)}$.

Here, $ordp(a)$ denotes the order of $[a]$ in the field $(F_p)^*$

What I have so far: Since $p$ is prime, the group $G=(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic. Therefore, $G^n=\{x^n : x \in G\} = <g^n> = <g^k>$ where $k=\gcd(m,n)$ where $m$ is order of $G$. In this case, $m=p-1$ so $k=\gcd(p-1,n)$

I don't know how to proceed further however. Any help would be appreciated!

$\endgroup$
4
  • $\begingroup$ Using the fact the group is cyclic is the right track. $\endgroup$ Oct 21, 2015 at 18:00
  • $\begingroup$ @AndréNicolas Could you elaborate a bit on how to proceed? I have given this some thought and still can't come up with anything $\endgroup$
    – jmsac
    Oct 21, 2015 at 21:08
  • $\begingroup$ I may try, though not immediately. One reason I did not is that I do not know what tools you have available. For example, when I have taught this material, I have usually first worked out the properties of indices, and then used these to prove the result. But I do not know whether you have had prior exposure to indices. $\endgroup$ Oct 21, 2015 at 21:21
  • $\begingroup$ @AndréNicolas No I haven't learned about indeces. Any help is appreciated thanks! $\endgroup$
    – jmsac
    Oct 21, 2015 at 21:30

1 Answer 1

2
$\begingroup$

Let $g$ be a generator of the multiplicative group, and let $a=g^s$. We are trying to find a number $e$ between $1$ and $p-1$ such that $(g^e)^n=g^s$.

So we want $g^{en}\equiv g^s\pmod{p}$. This holds if and only if $en\equiv s\pmod{p-1}$.

Now consider the congruence $en\equiv s\pmod{p-1}$, where $e$ should ne considered variable. This congruence has a solution if and only if $\gcd(n,p-1)$ divides $s$.

We therefore want to show that $\gcd(n,p-1)$ divides $s$ if and only if the order of $a$ divides $\frac{p-1}{\gcd(n,p-1)}$.

We will do one direction in detail, and leave the other direction to you. We show that if $\gcd(n,p-1)$ divides $s$, then the order of $a$ divides $\frac{p-1}{\gcd(n,p-1)}$.

It is enough to show that $a$ raised to the power $\frac{p-1}{\gcd(n,p-1)}$ is congruent to $1$ modulo $p$. So we want to show that $g^s$ raised to the power $\frac{p-1}{\gcd(n,p-1)}$ is congruent to $1$ modulo $p$. To do this we need to show that $s\cdot \frac{p-1}{\gcd(n,p-1)}$ is a multiple of $p-1$.

This is obvious. For we are told that $\gcd(n,p-1)$ divides $s$, say $s=a'\gcd(n,p-1)$. Then $$s\cdot \frac{p-1}{\gcd(n,p-1)}=s'\gcd(n,p-1)\cdot \frac{p-1}{\gcd(n,p-1)}=s'(p-1),$$ and $s'(p-1)$ is a multiple of $p-1$.

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