Query on Fermat's Little Theorem

Question

Fermat's Little Theorem States that,

If $p$ is a prime number and $gcd(a,p)=1$, then $a^{p-1}\equiv 1\ (mod p)$.

Suppose $a=10$.

My query is, if we assume that $p>a$, what assumptions should be made to conclude that $p-1$ is the least positive integer power such that $a^{p-1}\equiv 1\ (mod\ p)$?

Note that the conclusion fails to hold when $p<a$ for $10\equiv 10^2\equiv 1\ (mod\ 3)$.

Also for $p=11$, $10^2\equiv 10^{10}\equiv 1\ (mod\ 11)$.

But for $p=23$, the least positive integer such that $10^{p-1}\equiv 1\ (mod\ p)$ is $p-1=23-1=22$.

Answer 1

I'm not entirely clear what you mean by "what assumptions should be made...". However the following can be said.

• For any prime $p$ there exists $a$ with $1\le a<p$ with the following property: the least positive integer $m$ such that $a^m\equiv1\pmod p$ is $m=p-1$.

• If $a$ is one such number, then all such numbers are given by $a^g\pmod p$, where $1\le g<p-1$ and $\gcd(g,p-1)=1$.

For future reference, some terminology: the least positive integer $m$ such that $a^m\equiv1\pmod p$ is called the order of $a$ modulo $p$. An element having order $p-1$ is called a primitive root modulo $p$ or a generator of the multiplicative group modulo $p$.

So the above can be restated as: every prime has a primitive root; and given a specific primitive root $a$, all primitive roots are found from the formula in the second point above.

Given $p$, there is no simple formula for actually finding your "first" primitive root, it's basically trial and error. (Perhaps this is the answer to your question.) However there are some techniques which can make the trial and error a bit less awful. See here for some ideas.

Answer 2

There's no simple characterisation of the primes for which $10$ has order $p-1$, but there is a necessary condition, namely that $10$ be a quadratic non-residue modulo $p$, for is $10$ is a quadratic residue then $10^{(p-1)/2}\equiv1\pmod p$. In terms of Legendre symbols $$\left(\frac{10}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{5}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{p}{5}\right)$$ (using quadratic reciprocity). Thus $10$ is a quadratic residue modulo $p$ iff $p\equiv 1,3,9,13,27,31,37$ or $39\pmod{40}$. So there are infinitely many $p$ with $10^{(p-1)/2}\equiv1\pmod p$.