A power even smaller than Fermat's Little Theorem suggests?

Question

So I know that Fermat's little theorem states: let $p$ be a prime number, let $a$ be an integer where $p \nmid a$. So $a^{p-1} \equiv 1 $ (mod $p$).
But is it possible to prove that there is some smaller power of $a$ that is congruent to $1$ as well?

If I can find some integer $k$ where it is the smallest positive integer so that $a^k \equiv 1$ (mod $p$) then how can I prove that $k \mid (p-1) $ as that would complete the proof in stating that there IS some smaller power than $p-1$.

Answer 1

Of course it's possible for some $a$. For example, if $a = -1$, then we have $a^2 \equiv 1 \pmod{p}$ regardless of $p$. For others, $p-1$ is the smallest positive integer for which this holds, e.g. $2$ in $\mathbb{Z}_5$ or $3$ in $\mathbb{Z}_7$. If the latter is the case, we call $a$ a primitive root modulo $p$. This is number-theoretic terminology expressing the fact that $\mathbb{Z}_p^\times$ is a cyclic group and $a$ is a generator of it (which is not necessarily unique).

To answer your second question, let's suppose the multiplicative order of $a$ in $\mathbb{Z}_p^\times$ is $k < p-1$. The division algorithm lets us write $p\!-\!1 = qk + r$ for some $0 \leq r < k$ and $q \in \mathbb{N}$. Thus, $a^{p-1} = a^{qk + r} = a^{qk}a^r = (a^k)^qa^r = 1$. What's $(a^k)^q$? What must be true of $r$?

So it is true that the order will divide $p\!-\!1$. However, finding the multiplicative order of an element modulo $p$ is computationally difficult$^\dagger$. If we have at least been blessed with the prime factorization of $p\!-\!1$, we have to essentially brute force the possibilities, dividing off a given prime factor until the exponentiation no longer yields $1$, then moving on to the next prime factor.

---

$^\dagger$This is a discrete log problem. No polynomial-time algorithms for classical computers have yet been discovered for this task.

Answer 2

There isn't.

The group $\mathbb{Z}/p^{*}$ is cyclic.

See also: primitive roots and carmichael function.

Answer 3

For a fixed $a$, it is definitely possible. Notice that if $a=1$ then $k=1$ works. For a slightly less trivial example, $4^4=1\pmod{17}$. However, there is no smaller power that works for all values of $a$. Numbers that require an exponent of $p-1$ exactly are called primitive roots. It is a famous theorem that for every prime, there is at least one privative root (in fact there are several, because if $GCD(p,q)=1$ then $g$ is a primitive root (also called a "generator") if and only if $g^q$ is.

Now, suppose $a^k=1\pmod{p}$. We want to prove that $k|p-1$. Since $p$ is prime, we know that there exists some primitive root, $g$. If we look at the set $\{g,g^2,\ldots , g^{p-1}\}$ we see that every number in $\{1,\ldots p-1\}$ shows up precisely once. To prove that this is the case, notice that since there are $p-1$ possible values and $p-1$ locations, every number at least once if and only if every number shows up at most once. WLOG let $p>m>n>0$. If $g^m=g^n,$ then $g^{m-n}=1\pmod{p}$. But this contradicts the fact that $g$ is a generator. Thus every number shows up at most once and so every number shows up exactly once. Since every number shows up exactly once, for some $m$ $g^m=a$. Then $1=a^k=g^{km}$ so $km=p-1$ since $g$ is a generator. Thus $k|p-1$.