stuck on a proof..any help would be great!
show, for any integer k>=0:
en(a^k)= en(a) / gcd( en(a), k)
where en(a) is the order of a modulo n, also (a,n) = 1
Let en(a^k) = i and en(a) = j. Thus, and it is the least positive exponent. We therefore want, , this happens if and only if . Let . Therefore, . But so for this fraction to be a whole number we require to divide . The smallest such is therefore, . Which is what you wanted to prove.
I had another proof using group theory. Consider the cyclic subgroups and .
Define by This is well defined for if then
is surjective as Clearly it is also a homomorphism.
Let and
for some
_______
_______
Now there are integers such that
Conversely, if then = = = = 1.
Hence the kernel of is and the result follows (note that has elements).