Show that for any positive integer "a" such that gcd(a, p) = 1 and a^(p - 1) = 1 (mod p)?

If gcd(a,p) = 1, then a must be co prime to p. This is very similar to Fermat's little theorem (In fact I think it is Fermat's little theorem). In Fermat's little theorem, p is prime, not co prime to a.

This problem is very difficult to prove, even I can't remember the proof. However turns out that many people have summarise it:

http://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html

Also try this:

http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem

This is Fermat's little theorem. You can find the proofs of it here.

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem

Refer to Fermat's little theorem.