Is U(13) and U(15) Cyclic Groups?

[sarah77]

Homework Statement

Is U(13) cyclic? Is U(15) cyclic?

2. The attempt at a solution

The units in U(13): {1,2,3,4,5,6,7,8,9,10,11,12} U(13) is not cyclic because it is prime?
U15:{1,2,4,7,8,11,13,14} and there are no generators either? I do not think I am correct with this though.

 

[sarah77]

Does anyone know how to find a generator for U₁₃? I know the elements are
{1,2,3,4,5,6,7,8,9,10,11,12}. I have eliminated 1,2,3,4,5 and I am working on 6. I am doing it this way:

6⁰=1
6¹=6
6²=10
6³=8
6⁴=9
6⁵=2

..and so on, but I did, for example, 6²=36-13=23=10 and that is how I found 10. But when I get into larger numbers it is very time consuming to type, for example, 6⁴=1296-13=1283-13=1270-13...and so on. Does anyone know a faster way to solve these?

 

[Sethric]

Well, for prime numbers, the group of units is always cyclic. Actually that holds true for powers of odd primes as well. Therefore, it is just a matter of finding the generator. For composite numbers, I recommend looking into the Chinese Remainder Theorem to determine if it is cyclic.

 

[magicarpet512]

You have the right technique to generate U(13) using the element 6, but unfortunately it is a very tedious way of doing things. In my Abstract Algebra course, we had access to technology such as SAGE - an opensource math software that you can run on your internet browser. Also, Wolfram Alpha is another one that may speed up your calculations - just google it, then type something like mod(123^4,27) in the box and press enter, and it will calculate 123^4 in mod(27). Maybe that will speed things up a little bit.

 

[Sethric]

Also keep in mind that you don't have to keep going through all power iterations. Since you know the powers of any element of a group form a subgroup, then the order of that cyclic subgroup must divide the order of the group, i.e. once you found that cyclic group generated by 6 had more than 6 elements, you know it generates the entire group. If it helps, when dealing with groups formed by units, if it is cyclic, then the number of elements that generate the set is equal to the phi function of the order of the group. You can use information like this to help you. Say you find the order of element. If that element doesn't generate the set, it still is a cyclic subgroup. Therefore it is equal to a generator raised to the power of the index number of that subgroup. For example: in U¹³, 4⁶ = 1. Therefore 4 = g², implying 2 generates the group. Which raises a concern. How did you eliminate 2 as a generator?

 

[Slats18]

There is also a quicker way than yours, sarah77, and it is using the fact that 6^4 mod 13 = (6^3(mod 13)*6) mod 13

Instead of starting at 6^4=1296 and then subtracting 13, use what you found for 6^3 mod 13 (8) and then multiply that by 6, then start subtracting your values of 13. This result will be equal to 6^4 mod 13 =)

Ex. 6^3(mod 13)*6 = 8*6 = 48 = 9 mod 13