Hi, I am not sure about my answer.
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.
Is this adequate?
Thank you
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.