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

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.

• The smallest such (positive) $x$ is called the order of $a$; it will necessarily divide $p-1$, so you just need to test all the divisors of $p-1$. Oct 4, 2014 at 23:27
• I know it must be a divisor of p - 1, but is there no way of knowing if an x smaller than p - 1 exists besides testing all divisors of p - 1?
– tree
Oct 4, 2014 at 23:32
• Not that I'm aware of, except for some obvious special cases (like $a=1$ or $a=-1$). Oct 4, 2014 at 23:36

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
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}^*$.