Finding the group of residue classes modulo n under multiplication

Question

Is the group $(\mathbb{Z}/n\mathbb{Z})^\times = U(n)$ = the group of residue classes mod n under multiplication built into Mathematica?

As a first step, I want Mathematica to list the elements of this group when given parameter n. ie. $U(10) = \{1, 3, 7, 9\}$.

Then I want to be able to explore this group by checking things like is the group abelian, what is the order of the group, the order of each of its elements, what are the subgroups, etc..

I'm a programmer, but new to Mathematica. I did skim this page http://reference.wolfram.com/language/ref/FiniteGroupData.html but didn't see this particular group listed. So if it's not built in I'd be curious about how to program such a structure.

Answer 1

Exploration of $(\mathbb{Z}/n\mathbb{Z})^\times$

The multiplicative group of integers modulo $n$ is given in the paclet FiniteGroupData by {"CyclicGroupUnits", n}.

SetAttributes[u, HoldAllComplete];
u[n_Integer, prop_: Sequence[]] := FiniteGroupData[{"CyclicGroupUnits", n}, prop];

u[10]
(* {"CyclicGroupUnits", 10} *)

Available properties are given by FiniteGroupData["Properties"]. Here are a few of them for this group, the last two being mentioned in your question:

u[10, "Name"]
(* "group of units of the cyclic group of order 10" *)    

u[10, "Order"]
(* 4 *)

u[10, "Classes"]
(* {"Abelian", "Cyclic", "Nonalternating", "Nonperfect", "Nonsimple",
    "Nonsporadic", "Nonsymmetric", "Solvable", "Transitive"} *)

You can also ask for all property values in one shot with u[10, All].

About the elements

The elements of the group are given by

u[10, "Elements"]
(* {1, 2, 3, 4} *)

but this does not give what you are looking after. The reduced residue system modulo $n$ can be computed with

u[n_Integer, "Residues"] := With[{l = Range[n]}, Pick[l, CoprimeQ[l, n]]];

u[10, "Residues"]
(* {1, 3, 7, 9} *)

Visualization

The group can be visualized from the property CycleGraph:

u[10, "CycleGraph"]

We can try improving this graph by including the residues as vertex labels. The idea is to get something similar to the graphs we can see in this MathWorld entry.

We can proceed in three steps. There are probably shorter/more condensed approaches, but here we will use each step to define a new property, accessible independently from the generation of the graph.

First step. We first need to compute the subgroups generated by the residues:

u[n_Integer, "AllSubgroupsFromResidues"] := Module[{func}, 

    func = Function[p, Power[#, p] &] /@ Range[n];
    DeleteDuplicates /@ Mod[Through[func[#]] & /@ u[n, "Residues"], n]

];

u[10, "AllSubgroupsFromResidues"]
(* {{1}, {3, 9, 7, 1}, {7, 9, 3, 1}, {9, 1}} *)

Second step. We want to select among those the subgroups that are not subgroups of another subgroup:

u[n_Integer, "SubgroupsFromResidues"] := Module[{manip},

      manip[l_] /; (Length[l] == 1 || Length[l] == 0) := l;
      manip[l_] := With[{f = First[l], rest = Rest[l]},
         {f, Sequence @@ manip[Pick[rest, SubsetQ[f, #] & /@ rest, False]]}
      ];

      manip[Reverse@ SortBy[u[n, "AllSubgroupsFromResidues"], Length]]

];

u[10, "SubgroupsFromResidues"]
(* {{7, 9, 3, 1}} *)

Last step. We generate the graph:

u[n_Integer, "CycleGraphAlt"] := Module[{edges},

   edges = Partition[Append[#, #[[1]]], 2, 1] & /@ u[n, "SubgroupsFromResidues"];
   edges = UndirectedEdge @@@ Flatten[edges, 1];

   Graph[edges, 
      VertexSize -> 0.5, 
      VertexLabels -> 
         ((# -> Placed[Style[#, 12, "Panel", Background -> None], Center]) & /@ 
           VertexList[edges]
         )
   ]

];

For $U(10)$ we get:

u[10, "CycleGraphAlt"]

and for groups visually more interesting:

u[12, "CycleGraphAlt"]

u[15, "CycleGraphAlt"]

Appendix

The code blocks gathered:

SetAttributes[u, HoldAllComplete];

u[n_Integer, prop_: Sequence[]] := FiniteGroupData[{"CyclicGroupUnits", n}, prop];

u[n_Integer, "Residues"] := With[{l = Range[n]}, Pick[l, CoprimeQ[l, n]]];

u[n_Integer, "AllSubgroupsFromResidues"] := Module[{func}, 

    func = Function[p, Power[#, p] &] /@ Range[n];
    DeleteDuplicates /@ Mod[Through[func[#]] & /@ u[n, "Residues"], n]

];

u[n_Integer, "SubgroupsFromResidues"] := Module[{manip},

      manip[l_] /; (Length[l] == 1 || Length[l] == 0) := l;
      manip[l_] := With[{f = First[l], rest = Rest[l]},
         {f, Sequence @@ manip[Pick[rest, SubsetQ[f, #] & /@ rest, False]]}
      ];

      manip[Reverse@ SortBy[u[n, "AllSubgroupsFromResidues"], Length]]

];

u[n_Integer, "CycleGraphAlt"] := Module[{edges},

   edges = Partition[Append[#, #[[1]]], 2, 1] & /@ u[n, "SubgroupsFromResidues"];
   edges = UndirectedEdge @@@ Flatten[edges, 1];

   Graph[edges, 
      VertexSize -> 0.5, 
      VertexLabels -> 
         ((# -> Placed[Style[#, 12, "Panel", Background -> None], Center]) & /@ 
           VertexList[edges]
         )
   ]

];