first, simple example... here Z_7's elements
exponentiated 6 times, where 6 is the group
order:
1,1,1,1,1,1
2,4,1,2,4,1
3,2,6,4,5,1
4,2,1,4,2,1
5,4,6,2,3,1
6,1,6,1,6,1
there is only one number coprime with 6,
which is 5, and above, in the 5'th column
you can see all the group elements
exponentiated by 5, and the sequence is
unique {1,4,5,2,3,6} - so no matter what
element we pick, SOME other element to the
5'th power will equal it
but how to prove it for general cases? this
will be a joke to any real math person, but
here it goes..
since Z_p is a cyclic group, there is some
generator g such that {g,g^2,...,g^(p-1)}
is all the members of Z_p
p-1 is of course the number of elements in
the group (its order) and some people will
write the above generator sequence as
{1,g,g^2,...,g^(p-2)} (we just moved the
g^(p-1) up to the front)
so suppose we exponentiate every element
of the group by e, gcd(e,p-1)=1
then the elements of the group can be
written in terms of the generator as:
{1,g^e,g^(2e),...,g^((p-2)e)}
i want to show that this is all unique
elements (the group itself), so that like
the example, any element we pick can be
written as an element to this exponent e
to do this, assume that it is NOT true,
that there is a pair of members that are
equal in {1,g^e,g^(2e),...,g^((p-2)e)}
that means that there is some a,b with
0<=a<=(p-2) and 0<=b<=(p-2) and a!=b such
that:
g^(ae) = g^(be) (mod P)
just two elements of Z_p written in terms
of the generator and exponentiated by e
by Lagrange's theorem, this is true only
when:
ae = be (mod p-1)
here is the important part! since gcd(e,p-1)=1
then e has a multiplicative inverse and
can be cancelled from this equation, leaving:
a = b (mod p-1)
and since we picked a,b less than or equal
to p-1, and not identical, this is a
contradiction, meaning that our initial
assumption that two elements can be identical
is false
thus, again, the elements of the group Z_p
exponentiated by e generate the unique elements
of the group Z_p, so no matter which one we
pick, it is reachable by some other element
raised to the e power