1. ## modulo orders

Given a is an integer with (a,66)=1, what are the possible orders for a modulo 66?

Working:
Since phi(66)=20 then the possible orders of a modulo 66 have to divide this. So the possible orders are 1,2,4,5,10,20.

Thank you

2. ## Re: modulo orders

Originally Posted by alexgeek101
Yes.

Thanks alex.

4. ## Re: modulo orders

actually, no. some orders might not be possible, even from that list. for example, 20 is only possible if U(66) is cyclic, that is, has a generator.

for example, <5> = {1,5,25,59,31,23,49,47,37,53}, that is 5 has order 10 (mod 66).

since we have (5^k)^10 = 5^(10k) = (5^10)^k =1^k = 1 (mod 66), none of these numbers can have order 20.

(this does however, guarantee elements of orders of 2,5 and 10 exist).

also, <7> = {1,7,49,13,25,43,37,61,31,19} so 7 is of order 10, and none of THESE numbers have order 20.

now, any cyclic group of order 20 has φ(20) = 8 generators, but we've eliminated 15 out of the 20 elements of U(66)

as possibilities, so that leaves only 5 left and 5 < 8.

so order 20 is not a possibility (even though it looked like it could be).

is order 4 possible? since 4 does not divide 10, we have to look among the numbers we haven't tried so far:

17, 29, 35, 41, and 65.

now 17^2 = 25, 17^4 = (25)^2 = (5^2)^4 = 5^8 = 37. so 17 is not of order 2 or 4, so has to be of order 5 or 10.

17^5 = 35, so 17 is of order 10. one may check that <17> = {1,17,25,37,35,49,41,31,65},

so there are no elements of order 4, either.

so in actual point of fact, the only possible orders are: 1,2,5, and 10.

5. ## Re: modulo orders

Originally Posted by Deveno
since 4 does not divide 20...
Uh oh!

6. ## Re: modulo orders

in my defense, i point out that the "1" key and the "2" key on my keyboard are mere millimeters away.....i fixed it.