A stricter Fermat's little theorem: when does $a^n\equiv 1$ (mod $p$) for $n < p$?

Question

By Fermat's little theorem we know that

$a^{p-1} \equiv 1 \pmod{p}$ for all primes p.

But it is often possible to find $x$ such that $a^{x} \equiv 1 \pmod{p}$ and x < p - 1. Is there anyway to predict when such an $x$ exists or what it is? I wrote a program to generate the minimal such $x$ for all $a$ less than a prime $p$, but I can't figure out any pattern.

Answer 1

note that the numbers $1,2,...,p-1$ form a cyclic group whose operation is multiplication followed by reduction mod $p$

if you find a generator, $\alpha$, then $\alpha^k$ for $k=1,...,p-1$ gives all the elements of the group. the order of $\alpha^k$ is $\frac{n}{(n,k)}$

for example look at $F_7^{\times}$ whose elements are $1,2,3,4,5,6$ you can see that $3$ is a generator: $$ 3^2 \equiv_7 2 \\ 3^3 \equiv_7 6 \\ 3^4 \equiv_7 4 \\ 3^5 \equiv_7 5 \\ 3^6 \equiv_7 1 \\ $$ check out e.g. that $\frac6{(6,3)} = 2$ so $6^2 \equiv_7 1$. you can make up many examples to check. this is a good introduction to the study of finite fields

Answer 2

One can observe that $\forall$ x such that $x|p-1$ $\exists$ a such that $a^x\equiv 1 (modp)$ This by cauchy's theorem for finite group http://en.wikipedia.o/wiki/Cauchy%27s_theorem_%28group_theory%29 In our case , the Group is $\mathbb{Z}_{p}^*$.