# A small application of Fermat's Little Theorem

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.

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

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