Let be an odd prime and a positive integer. Use the Binomial Theorem to show that but that . Deduce that is an element of order in .
First we prove some lemmas.
Lemma 1: Let , , and be integers. If divides and , then divides . Proof: We have integers , , and such that and . Now and , so that .
Lemma 2: Let , let be a prime, and let . If divides times, then divides times. Proof: We proceed by induction on . For the base case , we have . For the inductive step, let . Suppose that divides times, divides times, and divides times. Note that . Now we have , , and , where does not divide , , and . Note that
Now (1) is an integer and , so by Lemma 1, divides . Moreover, does not divide or (as otherwise would divide ) so that, since is prime, does not divide . Thus the highest power of which divides is . Thus the lemma holds for , and by induction holds for all .
Lemma 3: Let be a prime and a positive integer. If divides times, then . Proof: Suppose to the contrary that ; then we have for some . Moreover, , a contradiction. So . .
Lemma 4: Let with and . Then . Proof: First we prove the case by induction. Note that if , we have . Suppose now that the lemma holds for some . Then ; thus the lemma holds for all and . Now let ; . Thus the lemma holds.
Lemma 5: Let be an odd prime and a positive integer. If divides times, then . Proof: Suppose . Then by Lemma 4, .
Now to the main result. Recall the Binomial Theorem:
In our case, we have
By Lemma 2 above, note that , where is the highest power of dividing and does not divide . Thus
Now since by Lemma 3, . So for all . Modulo , the only nonzero term is the term, which is clearly 1. Thus mod .
Consider now . As before, by Lemma 2, for each we have , where divides times and does not divide . By the Binomial theorem, we have
By Lemma 5 above, if then . Thus , so that, modulo , all terms with are 0. Thus we have
Hence mod .
Finally, recall that for any element in a group , if and only if divides . Thus we see that in , divides but not ; hence .