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

Printable View

- Apr 1st 2009, 06:20 PMminivan15help with a proof on orders
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 - Apr 2nd 2009, 08:11 PMThePerfectHacker
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.

- Apr 2nd 2009, 09:14 PMJaneBennet
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).