Group Theory + Fermat's Little Number Theorem

[mufusisrad]

This isn't a homework problem as it is me working through some math texts in order to add some "rigor" to my physics/engineering acumen. As an undergrad, I attempted to take a course in abstract algebra, but had to drop it due to scheduling problems. I've been working through my copy of Hungerford and am using Tinkham's "Group Theory and Quantum Mechanics" to supplement the rather minimal treatment of group theory while providing some good practical problems. This problem is from the first chapter of Tinkham.

Homework Statement

Consider a group of order (p-1), where p is a prime, with elements 1,2,..,(p-1) and group multiplcation is defined as multiplcation mod p. Prove that for any element of the group, A, the following relationship holds: A^(p-1)=E (the multiplicative identity).

Homework Equations

This is equivalent to proving that for a given integer, N, and a prime, P, that N^P is congruent to N modulo P.

The Attempt at a Solution

The solution I have is very simple, but I feel as if it is missing something

-Assume that any element, A, generates a cyclic subgroup of order k, s.t. A^k=E.
-By Lagrange's theorem, k must be an integer divisor of (p-1), the order of the larger group. This leads to n*k=(p-1).
-A^(p-1)=A*(n*k)=(A^k)^n=(E)^n=E, Q.E.D.

I like the proof, but the first statement doesn't seem complete. I don't feel comfortable just assuming that any element can generate such a subgroup. Can anyone help me justify this?

 

[Hurkyl]

I don't feel comfortable just assuming that any element can generate such a subgroup.

Firstly, there's a general definition:

Given a subset S of a group G, the subgroup of G generated by S is defined to be the smallest subgroup of G that contains S.

You can prove that the subgroup generated by S always exists -- but here we don't have to resort to such generalities. You can explicitly write down the subgroup generated by A! And for the purposes of this proof, you don't even care that it's the smallest; all you care is that the powers of A form a group.

 

[matt grime]

-Assume that any element, A, generates a cyclic subgroup of order k, s.t. A^k=E.

this is not an assumption. Any element A does generate a subgroup of some order

-By Lagrange's theorem, k must be an integer divisor of (p-1), the order of the larger group. This leads to n*k=(p-1).
-A^(p-1)=A*(n*k)=(A^k)^n=(E)^n=E, Q.E.D.

This is perfectly correct but sort of too good. Yes, you invoke Lagrange's theorem, but Lagrange's theorem is a generalization of the idea that the order of an element divides the order of the group (which is all you're asking).

You can find much more interesting proofs than this using a little number theory or combinatorics or even just the binomial theorem:

A^p = (A-1 +1)^p=(A-1)^p + 1 = A-1+1 =A (all '=' are congruence mod p)

Here you should verify that the 'naive' mistake of writing (x+y)^p=x^p+y^p is actually vali: p choose r is p! divided by smaller factorials, so the p in p! never cancels unless r=0 or p.
The third equality is just induction, by the way.

I suspect that is the proof they had in mind - after all you never use the fact that you're operating 'mod p' for p a prime do you? You've just proven that x^|G|=1 for any group G, which is far more powerful. Has the book even mentioned Lagrange's theorem at this point?

 

[mufusisrad]

Thanks for both of your responses! I feel much more comfortable with my initial statement. When I first saw the problem, I actually ended up doing the binomial theorem proof first, but wanted to see if I could do it using only the theorems that had been brought up in the book up until that point. Tinkham doesn't actually refer to Lagrange's Theorem by name, but he does prove it in the second chapter so he can use it when he introduces factor groups. What did either of you use for your first texts in Group Theory?

 

[matt grime]

So you used a technique in chapter 2 to prove a result in chapter 1? That surely points to you that you weren't supposed to use Lagrange's theorem.

I didn't have a text for group theory. I still don't. I had lecture notes.