Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.