4
$\begingroup$

Problem statement. Suppose that $k$ is a positive integer and $p$ a prime such that $a^k\equiv a\mod p$ for all positive integers $a$. Show that $(p - 1)$ divides $(k-1)$.

The proof is simple if we can use the fact that $U(p):=(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic. In that case, we simply observe that $|U(p)|=p-1$ and select any generator $a$. It is a well-known result that if in a finite cyclic group generated by $a$ we have $a^i=a^j$, then the order of $a$ divides $i-j$. Hence $p-1$ divides $k-1$.

The problem is, the student who needs to prove this result isn't allowed to use the fact that $U(p)$ is cyclic. And all the proofs I know for $U(p)$ being cyclic are way too advanced for him, so he isn't able to prove it for himself. Hence I am asking:

Question. Is there an elementary proof of the above, appropriate to an undergraduate abstract algebra course, that doesn't use the fact that $U(p)$ is cyclic?

(Then again, maybe I am wrong that it is too advanced for him to prove that $U(p)$ is cyclic. If you have any ideas there, they are welcome too.)

Thanks guys!

$\endgroup$
1
  • 4
    $\begingroup$ You are clearly assuming that $p$ is prime, but you should say so! $\endgroup$
    – Derek Holt
    Mar 17 at 13:38

1 Answer 1

Reset to default
5
$\begingroup$

Well...Since, for non-zero $a$, we have $a^{p-1}\equiv a^{k-1}\equiv 1\pmod p$ we can deduce that $a^d\equiv 1 \pmod p$ for $d=\gcd(p-1,k-1)$. Here, of course, $1≤d≤p-1$.

But you know that $\mathbb Z/p\mathbb Z$ is a field (at least, I assume your students know that) so $a^d\equiv 1 \pmod p$ can't have more than $d$ roots. The desired conclusion follows.

That's the same principle which underlies the standard proof that primitive roots exist, but this case is more elementary (I'd say). Indeed, this argument might serve as a good introduction to the proof of the primitive root theorem.

$\endgroup$
3
  • $\begingroup$ This is very good, thank you. Unfortunately the chapter on Fields isn't till later in the course, so the student does not have the no-more-than-d-roots theorem available. But I will try to think if there is an elementary proof for that, which most likely there should be. Thanks again! $\endgroup$
    – Ben W
    Mar 17 at 15:45
  • $\begingroup$ The second paragraph is at the hart of most of the proofs that $U(p)$ is cyclic, so it is as "advanced" as the one to be avoided. $\endgroup$
    – citadel
    Mar 17 at 21:09
  • $\begingroup$ @Devo I disagree, though, as mentioned in my solution, I agree that the same core principle underlies both arguments. The standard proof of the Primitive root theorem requires abstraction...namely, you must introduce a new function which counts the elements of a given order and then you argue that this must coincide with Euler's totient function, for which you must prove that $\sum_{d|n}\varphi(d)=n$ which, again, is quite abstract and non-trivial. My argument rests only on a basic fact of Field Algebra. Since the claim is false for composites, I think one needs something like this. $\endgroup$
    – lulu
    Mar 18 at 14:24

You must log in to answer this question.

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