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

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

• There isn't always a smaller power, but there can be. Commented Mar 10, 2017 at 2:31
• $k\mid (p-1)$ would not prove that, since trivially $(p-1)\mid (p-1)$. If you're looking for a smaller $k(a)$ that works for a single $a$, then for some $a$ you can find it. Trivially, $1^1\equiv 1\pmod p$ and, $k(a^2)=\frac{p-1}2$ works for $p\ne2$. However, if you are looking for a $k$ which works for all $a$ coprime with $p$, you are ultimatley interested in Carmichael's function. However, Aryabhata answered the question for primes $p$.
– user228113
Commented Mar 10, 2017 at 2:33

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.

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

There isn't.

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

See also: primitive roots and carmichael function.