1
$\begingroup$

Suppose that $q$ is some prime number distinct from prime $p$ (in particular, assume $q < p$). I would like to show that the elements $q^1, q^2, ... , q^{p-1}$ modulo $p$ are all distinct from each other. This is what I have so far:

If $q^i \equiv q^j \mod p$ then $q^i - q^j \equiv 0 \mod p$. WLOG assume that $i < j$ so that we can fact

$q^i(1 - q^{j-i}) \equiv 0 \mod p$

which, since $p$ does not divide $q$, implies that $q^{j-i} \equiv 1 \mod p$.

Here I am tempted to say that $j-i$ must be some multiple of $p$, but am unable to rigorously justify it. Help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ What you're trying to show is not true in general. Consider $q = 2$ and $p = 7$. $\endgroup$ – user43208 Oct 16 '13 at 0:28
0
$\begingroup$

You said that $q^{j-i} \equiv 1 \mod p$, that means that $j-i$ is multiplicative order of q modulo p or its multiple, but not every number is a multiplicative order of q modulo p or its multiple. So in order for this to be true the following needs to hold $j-i = k \cdot ord_p(q)$ for some natural number $k$

Also your assumtion $q^i \equiv q^j \pmod p$ will hold if and only if $i \equiv j \pmod {ord_p(q)}$.

And what you are actually trying to prove is that $q$ is primitive root modulo $p$, but only few numbers have that property and it doesn't hold for every number. Also it's good to know there's no specific way to find primitive root modulo $p$.

For more information read about multiplicative order and primitive root.

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