5
$\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$
  • $\begingroup$ There isn't always a smaller power, but there can be. $\endgroup$ – Thomas Andrews Mar 10 '17 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 Mar 10 '17 at 2:33
5
$\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$
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.