3
$\begingroup$

Question: "Show that if $p$ is prime and $\gcd(d,p-1) = 1$, then every positive integer less than p is congruent modulo $p$ to the $d$-th power of some other integer."

I understand that this is related with primitive roots but I get confused when trying to explain the theory. I was wondering if someone would be point me in the general direction? Thanks!

3 Answers 3

5

Let $a$ be a positive integer less than $p$.

Since $d$ and $p-1$ are relatively prime, there exist integers $x$ and $y$ such that $dx+(p-1)y=1$. Without loss of generality we may assume that $x$ is positive. Putting $z=-y$, we get $dx=1+(p-1)z$. Since $a^{(p-1)z}\equiv 1\pmod{p}$, we have $a\equiv a^{1+(p-1)z}\pmod{p}.$ But $a^{1+(p-1)z}=a^{dx}=(a^x)^{d}.$

2

Hints:

1) If we have a finite cyclic group $\,G=\langle x\,\rangle\,$ of order $\,n\,$, then

$G=\langle x^k\rangle\Longleftrightarrow (n,k)=1$

2) The multiplicative group $\,\left(\Bbb Z/p\Bbb Z\right)^*\,$ has order $\,p-1\,$

3) Your claim is trivially true for zero...

0

Let $r$ be a primitive root $\mod p$. Since $(d,p-1)=1 \Rightarrow r^d$ is a primitive root $\mod p$. Therefore $\{1,r^d,(r^d)^2,\ldots,(r^d)^{p-1}\}\equiv\{1,2,3,\ldots,p-1\} \pmod p$.