# A guess about prime number and modular arithmetic.

I have following guess:

Let $p>2$ be a prime number. Then there exist an integer $1 < a < p$ such that for any two different integer $x, y \in [p-1]$, we have $a^x \ne a^y \pmod{p}$.

I tried the first few examples, like $p=5, a = 3$, and $p=7, a=5$, and $p=19, a=2$, all fulfills the above conditions. So is there anything number theory could say something about this?

-
Such an $a$ is called a "generator" of the group of units modulo $p$, and yes, there is always such an $a$. –  Thomas Andrews Feb 7 '13 at 16:32
In older language such generators are called primitive roots mod n, e.g. see this Wikipedia page. –  Math Gems Feb 7 '13 at 16:59

There are deep reasons that this is true, but the fundamental reason is that the integers modulo $p$ form something called a field, and, in fields, there can be no more than $n$ solutions to the equation $x^{n}-1=0$ for any $n$. This can be used to show that there must be a solution to $x^{p-1}-1=0$ which is not a solution to any $x^{d}-1$ for $d<p-1$. Such a solution would give you your $a$.

This $a$ is called a "generator" because when you list $a,a^2,a^3,\dots,a^{p-1} \pmod p$, you get $p-1$ distinct values which thus cover all of the nonzero elements, modulo $p$.

-

Yes, the group of units of $\mathbf{Z}_{p}$ (where $\mathbf{Z}_{p}$ are the integers modulo $p$) is cyclic of order $p-1$, and your $a$ is a generator.

-

The integers mod p are a finite field. A finite subgroup of the multiplicative group of a field is cyclic. See this answer for a simple proof.

-