6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ There isn't always a smaller power, but there can be. $\endgroup$ Commented Mar 10, 2017 at 2:31
  • 1
    $\begingroup$ $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$. $\endgroup$
    – user228113
    Commented Mar 10, 2017 at 2:33

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

There isn't.

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

See also: primitive roots and carmichael function.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .