Tài liệu Oder of group

Remember: Given integers n and k, consider the operation o_k: Z_n x Z_n -> Z_n, (a, b) -> a + k^a * b (mod n). (Z_n, o_k) is a group if k^n == 1 (mod n) and k^k == k (mod n). The first condition is necessary to get the definition well-defined. The second condition is necessary for the associative property. For small n the following list shows n, k and the usual name of the group. Note that different k can result in groups that are isomorphic to each other. n=2, k=1: Z2 n=3, k=1: Z3 n=4, k=1: Z4 n=4, k=3: Z2 x Z2 n=5, k=1: Z5 n=6, k=1: Z6 n=6, k=5: D3 n=7, k=1: Z7 n=8, k=1: Z8 n=8, k=3: Q4 n=8, k=5: Z8 n=8, k=7: D4 n=9, k=1: Z9 n=9, k=4: Z9 n=9, k=7: Z9 n=10, k=1: Z10 n=10, k=9: D5 n=11, k=1: Z11 n=12, k=1: Z12 n=12, k=5: Q6 n=12, k=7: Z2 x Z6 n=12, k=11: D6 n=13, k=1: Z13 n=14, k=1: Z14 n=14, k=13: D7 n=15, k=1: Z15 n=16, k=1: Z16 n=16, k=5: Z16 n=16, k=7: Q8 n=16, k=9: Z16 n=16, k=13: Z16 n=16, k=15: D8 n=17, k=1: Z17 n=18, k=1: Z18 n=18, k=7: Z18 n=18, k=13: Z18 n=18, k=17: D9 n=19, k=1: Z19 n=20, k=1: Z20 n=20, k=9: Q10 n=20, k=11: Z2 x Z10 n=20, k=13: Typ 20 / 5 n=20, k=17: Typ 20 / 5 n=20, k=19: D10 n=21, n=21, n=21, n=22, n=22, n=23, n=24, n=24, n=24, n=24, n=24, n=24, n=24, n=24, n=25, n=25, n=25, n=25, n=25, n=26, n=26, n=27, n=27, n=27, n=28, n=28, n=28, n=28, n=29, n=30, n=30, n=30, n=30, n=31, n=32, n=32, n=32, n=32, n=32, n=32, k=1: Z21 k=4: TypN 21 / 2 k=16: TypN 21 / 2 k=1: Z22 k=21: D11 k=1: Z23 k=1: Z24 k=5: Typ 24 / 14 k=7: Z3 x D4 k=11: Q12 k=13: Z24 k=17: Typ 24 / 14 k=19: Z3 x Q4 k=23: D12 k=1: Z25 k=6: Z25 k=11: Z25 k=16: Z25 k=21: Z25 k=1: Z26 k=25: D13 k=1: Z27 k=10: Z27 k=19: Z27 k=1: Z28 k=13: Q14 k=15: Z2 x Z14 k=27: D14 k=1: Z29 k=1: Z30 k=11: Z5 x D3 k=19: Z3 x D5 k=29: D15 k=1: Z31 k=1: Z32 k=9: Z32 k=15: Q16 k=17: Z32 k=25: Z32 k=31: D16 This list was generated with the following Mathematica-Statements: (* Note that the identification is based on the element orders. Different groups can have the same element orders. E.g. "Z4 x Z4", "Z2 x Q4", "Typ 16 / 10" all have 1 element of order 1, 3 elements of order 2 and 12 elements of order 4. In this case, in addition to the element order, there has to be investigated further information. For example: is the group abelian, or how many different square-values are in the group. I.e., "Z4 x Z4" is abelian, "Z2 x Q4" and "Typ 16 / 10" are not. "Z2 x Q4" and "Typ 16 / 10" differ in the number of possible square values: 2 or 3 respectively. However, the groups that can be composed in the special operation (a,b)>a+k^a*b do not reach such ambigous groups for n<=32. Ordnungen = { {{}}, "Ordnungen 1-7", {{1, 1}}, "Z1", {{1, 1}, {1, 2}}, "Z2", {{1, 1}, {2, 3}}, "Z3", {{1, 1}, {1, 2}, {2, 4}}, "Z4", {{1, 1}, {3, 2}}, "Z2 x Z2", {{1, 1}, {4, 5}}, "Z5", {{1, 1}, {1, 2}, {2, 3}, {2, 6}}, "Z6", {{1, 1}, {3, 2}, {2, 3}}, "D3", {{1, 1}, {6, 7}}, "Z7", {{}}, "Ordnung 8", {{1, 1}, {1, 2}, {2, 4}, {4, 8}}, "Z8", {{1, 1}, {3, 2}, {4, 4}}, "Z2 x Z4", {{1, 1}, {7, 2}}, "Z2 x Z2 x Z2", {{1, 1}, {5, 2}, {2, 4}}, "D4", {{1, 1}, {1, 2}, {6, 4}}, "Q4", {{}}, "Ordnungen 9-11", {{1, 1}, {2, 3}, {6, 9}}, "Z9", {{1, 1}, {8, 3}}, "Z3 x Z3", {{1, 1}, {1, 2}, {4, 5}, {4, 10}}, "Z10", {{1, 1}, {5, 2}, {4, 5}}, "D5", {{1, 1}, {10, 11}}, "Z11", {{}}, "Ordnung 12", {{1, 1}, {1, 2}, {2, 3}, {2, 4}, {2, 6}, {4, 12}}, "Z12", {{1, 1}, {3, 2}, {2, 3}, {6, 6}}, "Z2 x Z6", {{1, 1}, {1, 2}, {2, 3}, {6, 4}, {2, 6}}, "Q6", {{1, 1}, {3, 2}, {8, 3}}, "A4", {{1, 1}, {7, 2}, {2, 3}, {2, 6}}, "D6", {{}}, "Ordnungen 13-15", {{1, 1}, {12, 13}}, "Z13", {{1, 1}, {1, 2}, {6, 7}, {6, 14}}, "Z14", {{1, 1}, {7, 2}, {6, 7}}, "D7", {{1, 1}, {2, 3}, {4, 5}, {8, 15}}, "Z15", {{}}, "Ordnung 16", {{1, 1}, {1, 2}, {2, 4}, {4, 8}, {8, 16}}, "Z16", {{1, 1}, {3, 2}, {4, 4}, {8, 8}},(*x,ab.,4 Q.*) "Z2 x Z8", {{1, 1}, {3, 2}, {12, 4}},(*o,ab.,4 Q.*) "Z4 x Z4", {{1, 1}, {7, 2}, {8, 4}},(*$,ab.,2 Q.*) "Z2 x Z2 x Z4", {{1, 1}, {15, 2}}, "Z2 x Z2 x Z2 x Z2", {{1, 1}, {11, 2}, {4, 4}}, "Z2 x D4", {{1, 1}, {3, 2}, {12, 4}},(*o,n.ab.,2 Quadratzahlen*) "Z2 x Q4", {{1, 1}, {7, 2}, {8, 4}},(*$,n.ab.,Zentrum~Z4, 2 Quadratzahlen*)"Typ 16 / 8", {{1, 1}, {7, 2}, {8, 4}},(*$,n.ab., Zentrum~Z2 x Z2,3 Quadratzahlen*) "Typ 16 / 9", {{1, 1}, {3, 2}, {12, 4}},(*o,n.ab.,3 Quadratzahlen*) "Typ 16 / 10", {{1, 1}, {3, 2}, {4, 4}, {8, 8}},(*x,n.ab.,4 Q.*) "Typ 16 / 11", {{1, 1}, {9, 2}, {2, 4}, {4, 8}}, "D8", {{1, 1}, {5, 2}, {6, 4}, {4, 8}}, "Typ 16 / 13", {{1, 1}, {1, 2}, {10, 4}, {4, 8}}, "Q8", {{}}, "Ordnung 17", {{1, 1}, {16, 17}}, "Z17", {{}}, "Ordnung 18", {{1, 1}, {1, 2}, {2, 3}, {2, 6}, {6, 9}, {6, 18}}, "Z18", {{1, 1}, {1, 2}, {8, 3}, {8, 6}}, "Z3 x Z6", {{1, 1}, {3, 2}, {8, 3}, {6, 6}}, "Z3 x S3", {{1, 1}, {9, 2}, {2, 3}, {6, 9}}, "D9", {{1, 1}, {9, 2}, {8, 3}}, "Typ 18 / 5", {{}}, "Ordnung 19", {{1, 1}, {18, 19}}, "Z19", {{}}, "Ordnung 20", {{1, 1}, {1, 2}, {2, 4}, {4, 5}, {4, 10}, {8, 20}}, "Z20", {{1, 1}, {3, 2}, {4, 5}, {12, 10}}, "Z2 x Z10", {{1, 1}, {11, 2}, {4, 5}, {4, 10}}, "D10", {{1, 1}, {1, 2}, {10, 4}, {4, 5}, {4, 10}}, "Q10", {{1, 1}, {5, 2}, {10, 4}, {4, 5}}, "Typ 20 / 5", {{}}, "Ordnungen 21-23", {{1, 1}, {2, 3}, {6, 7}, {12, 21}}, "Z21", {{1, 1}, {14, 3}, {6, 7}}, "TypN 21 / 2", {{1, 1}, {1, 2}, {10, 11}, {10, 22}}, "Z22", {{1, 1}, {11, 2}, {10, 11}}, "D11", {{1, 1}, {22, 23}}, "Z23", {{}}, "Ordnung 24", {{1, 1}, {1, 2}, {2, 3}, {2, 4}, {2, 6}, {4, 8}, {4, 12}, {8, 24}}, "Z24", {{1, 1}, {3, 2}, {2, 3}, {4, 4}, {6, 6}, {8, 12}}, "Z2 x Z12", {{1, 1}, {7, 2}, {2, 3}, {14, 6}}, "Z2 x Z2 x Z6", {{1, 1}, {15, 2}, {2, 3}, {6, 6}}, "Z2 x D6", {{1, 1}, {7, 2}, {8, 3}, {8, 6}}, "Z2 x A4", {{1, 1}, {3, 2}, {2, 3}, {12, 4}, {6, 6}}, "Z2 x Q6", {{1, 1}, {5, 2}, {2, 3}, {2, 4}, {10, 6}, {4, 12}}, "Z3 x D4", {{1, 1}, {1, 2}, {2, 3}, {6, 4}, {2, 6}, {12, 12}}, "Z3 x Q4", {{1, 1}, {7, 2}, {2, 3}, {8, 4}, {2, 6}, {4, 12}}, "Z4 x S3", {{1, 1}, {13, 2}, {2, 3}, {2, 4}, {2, 6}, {4, 12}}, "D12", {{1, 1}, {1, 2}, {2, 3}, {14, 4}, {2, 6}, {4, 12}}, "Q12", {{1, 1}, {9, 2}, {8, 3}, {6, 4}}, "S4", {{1, 1}, {1, 2}, {8, 3}, {6, 4}, {8, 6}}, "Typ 24 / 13", {{1, 1}, {1, 2}, {2, 3}, {2, 4}, {2, 6}, {12, 8}, {4, 12}}, "Typ 24 / 14", {{1, 1}, {9, 2}, {2, 3}, {6, 4}, {6, 6}}, "Typ 24 / 15", {{}}, "Ordnung 25", {{1, 1}, {4, 5}, {20, 25}}, "Z25", {{1, 1}, {24, 5}}, "Z5 x Z5", {{}}, "Ordnung 26", {{1, 1}, {1, 2}, {12, 13}, {12, 26}}, "Z26", {{1, 1}, {13, 2}, {12, 13}}, "D13", {{}}, "Ordnung 27", {{1, 1}, {2, 3}, {6, 9}, {18, 27}}, "Z27", {{1, 1}, {8, 3}, {18, 9}},(* *,abelsch*) "Z3 x Z9", {{1, 1}, {26, 3}},(*o,abelsch*) "Z3 x Z3 x Z3", {{1, 1}, {26, 3}},(*o,nicht ab.*) "Typ 27 / 4", {{1, 1}, {8, 3}, {18, 9}},(* *,nicht ab.*) "Typ 27 / 5", {{}}, "Ordnung 28", {{1, 1}, {1, 2}, {2, 4}, {6, 7}, {6, 14}, {12, 28}}, "Z28", {{1, 1}, {3, 2}, {6, 7}, {18, 14}}, "Z2 x Z14", {{1, 1}, {15, 2}, {6, 7}, {6, 14}}, "D14", {{1, 1}, {1, 2}, {14, 4}, {6, 7}, {6, 14}}, "Q14", {{}}, "Ordnung 29", {{1, 1}, {28, 29}}, "Z29", {{}}, "Ordnung 30", {{1, 1}, {1, 2}, {2, 3}, {4, 5}, {2, 6}, {4, 10}, {8, 15}, {8, 30}}, "Z30", {{1, 1}, {5, 2}, {2, 3}, {4, 5}, {10, 6}, {8, 15}}, "Z3 x D5", {{1, 1}, {3, 2}, {2, 3}, {4, 5}, {12, 10}, {8, 15}}, "Z5 x D3", {{1, 1}, {15, 2}, {2, 3}, {4, 5}, {8, 15}}, "D15", {{}}, "Ordnung 31", {{1, 1}, {30, 31}}, "Z31", {{}}, "Ordnung 32", {{1, 1}, {1, 2}, {2, 4}, {4, 8}, {8, 16}, {16, 32}}, "Z32", {{1, 1}, {3, 2}, {4, 4}, {8, 8}, {16, 16}}, "Z2 x Z16", {{1, 1}, {3, 2}, {12, 4}, {16, 8}}, "Z4 x Z8", {{1, 1}, {7, 2}, {8, 4}, {16, 8}}, "Z2 x Z2 x Z8", {{1, 1}, {7, 2}, {24, 4}}, "Z2 x Z4 x Z4", {{1, 1}, {15, 2}, {16, 4}}, "Z2 x Z2 x Z2 x Z4", {{1, 1}, {31, 2}}, "Z2 x Z2 x Z2 x Z2 x Z2", {{1, 1}, {23, 2}, {8, 4}}, "Z2 x Z2 x D4", {{1, 1}, {7, 2}, {24, 4}}, "Z2 x Z2 x Q4", {{1, 1}, {15, 2}, {16, 4}}, "Typ 32 / 10", {{1, 1}, {15, 2}, {16, 4}}, "Typ 32 / 11", {{1, 1}, {7, 2}, {24, 4}}, "Typ 32 / 12", {{1, 1}, {7, 2}, {8, 4}, {16, 8}}, "Typ 32 / 13", {{1, 1}, {11, 2}, {20, 4}}, "Z4 x D4", {{1, 1}, {3, 2}, {28, 4}}, "Z4 x Q4", {{1, 1}, {7, 2}, {24, 4}}, "Typ 32 / 16", {{1, 1}, {7, 2}, {8, 4}, {16, 8}}, "Typ 32 / 17", {{1, 1}, {7, 2}, {24, 4}}, "Typ 32 / 18", {{1, 1}, {3, 2}, {12, 4}, {16, 8}}, "Typ 32 / 19", {{1, 1}, {7, 2}, {8, 4}, {16, 8}}, "Typ 32 / 20", {{1, 1}, {3, 2}, {12, 4}, {16, 8}}, "Typ 32 / 21", {{1, 1}, {3, 2}, {4, 4}, {8, 8}, {16, 16}}, "Typ 32 / 22", {{1, 1}, {19, 2}, {4, 4}, {8, 8}}, "Z2 x D8", {{1, 1}, {11, 2}, {12, 4}, {8, 8}}, "Typ 32 / 24", {{1, 1}, {3, 2}, {20, 4}, {8, 8}}, "Z2 x Q8", {{1, 1}, {11, 2}, {12, 4}, {8, 8}}, "Typ 32 / 26", {{1, 1}, {11, 2}, {12, 4}, {8, 8}}, "Typ 32 / 27", {{1, 1}, {3, 2}, {20, 4}, {8, 8}}, "Typ 32 / 28", {{1, 1}, {3, 2}, {20, 4}, {8, 8}}, "Typ 32 / 29", {{1, 1}, {3, 2}, {20, 4}, {8, 8}}, "Typ 32 / 30", {{1, 1}, {7, 2}, {16, 4}, {8, 8}}, "Typ 32 / 31", {{1, 1}, {3, 2}, {4, 4}, {24, 8}}, "Typ 32 / 32", {{1, 1}, {19, 2}, {12, 4}}, "Typ 32 / 33", {{1, 1}, {19, 2}, {12, 4}}, "Typ 32 / 34", {{1, 1}, {3, 2}, {28, 4}}, "Typ 32 / 35", {{1, 1}, {15, 2}, {16, 4}}, "Typ 32 / 36", {{1, 1}, {7, 2}, {24, 4}}, "Typ 32 / 37", {{1, 1}, {11, 2}, {20, 4}}, "Typ 32 / 38", {{1, 1}, {11, 2}, {20, 4}}, "Typ 32 / 39", {{1, 1}, {3, 2}, {28, 4}}, "Typ 32 / 40", {{1, 1}, {7, 2}, {24, 4}}, "Typ 32 / 41", {{1, 1}, {19, 2}, {12, 4}}, "Typ 32 / 42", {{1, 1}, {11, 2}, {20, 4}}, "Typ 32 / 43", {{1, 1}, {15, 2}, {8, 4}, {8, 8}}, "Typ 32 / 44", {{1, 1}, {7, 2}, {16, 4}, {8, 8}}, "Typ 32 / 45", {{1, 1}, {11, 2}, {20, 4}}, "Typ 32 / 46", {{1, 1}, {11, 2}, {4, 4}, {16, 8}}, "Typ 32 / 47", {{1, 1}, {3, 2}, {12, 4}, {16, 8}}, "Typ 32 / 48", {{1, 1}, {17, 2}, {2, 4}, {4, 8}, {8, 16}}, "D16", {{1, 1}, {9, 2}, {10, 4}, {4, 8}, {8, 16}}, "Typ 32 / 50", {{1, 1}, {1, 2}, {18, 4}, {4, 8}, {8, 16}}, "Q16", {{}}, "sonstige Ordnungen", {{}}, "Ende"}; (* How to determine groups with same element orders: *) (* Select[CaseCount[Ordnungen], #[[1]] > 1 && #[[2]] != {{}} &]; Map[GroupName[#[[2]]] &, %] *) (* Result: {{"Z3 x Z3 x Z3", "Typ 27 / 4"}, {"Z4 x Z4", "Z2 x Q4", "Typ 16 / 10"}, {"Z4 x Q4", "Typ 32 / 35", "Typ 32 / 40"}, {"Z2 x Z2 x Z4", "Typ 16 / 8", "Typ 16 / 9"}, {"Z2 x Z4 x Z4", "Z2 x Z2 x Q4", "Typ 32 / 12", "Typ 32 / 16", "Typ 32 / 18", "Typ 32 / 37", "Typ 32 / 41"}, {"Z3 x Z9", "Typ 27 / 5"}, {"Z4 x D4", "Typ 32 / 38", "Typ 32 / 39", "Typ 32 / 43", "Typ 32 / 46"}, {"Z2 x Z2 x Z2 x Z4", "Typ 32 / 10", "Typ 32 / 11", "Typ 32 / 36"}, {"Typ 32 / 33", "Typ 32 / 34", "Typ 32 / 42"}, {"Z2 x Z8", "Typ 16 / 11"}, {"Z4 x Z8", "Typ 32 / 19", "Typ 32 / 21", "Typ 32 / 48"}, {"Z2 x Q8", "Typ 32 / 28", "Typ 32 / 29", "Typ 32 / 30"}, {"Z2 x Z2 x Z8", "Typ 32 / 13", "Typ 32 / 17", "Typ 32 / 20"}, {"Typ 32 / 31", "Typ 32 / 45"}, {"Typ 32 / 24", "Typ 32 / 26", "Typ 32 / 27"}, {"Z2 x Z16", "Typ 32 / 22"}} *) ElementOrder::usage = "ElementOrder[element, neutralElement, operation] returns the number n of necessary executions of 'operation[x,element]' to obtain 'neutralElement' by starting with x=element. ElementOrder[element, neutralElement, operation, MaxIterations -> 10000] will stop after at most MaxIterations calls of 'operation'. "; Options[ElementOrder] = {MaxIterations -> Infinity}; ElementOrder[element_, neutral_, operation_, opts___] := Block[{i = 1, power = element, aIMax = (MaxIterations /. {opts} /. Options[ElementOrder])}, While[(power != neutral) && (i < aIMax), i++; power = operation[power, element]]; i]; ElementOrders::usage = "ElementOrders[ElementList, neutral, operation] evaluates the appropriate ElementOrder for every element out of 'ElementList'. ElementOrder[element, neutralElement, operation, MaxIterations -> 10000] will stop searching for one ElementOrder after at most MaxIterations calls of 'operation'. "; ElementOrders[ElementList_List, neutral_, operation_, opts___] := Map[ElementOrder[#, neutral, operation, opts] &, ElementList]; CaseCount::usage = "CaseCount[list] returns a list with the pairs {#, elem} for every distinct 'elem' out of list, where # indicates the number of its occurrences in 'list'."; CaseCount[V_List] := Map[{Count[V, #], #} &, Union[V]]; GroupName::usage = "GroupName[CaseCountOrders] gives the names of all the groups with matching number of Element-Orders (due to A. D. Thomas and G. V. Wood: 'Group Tables'). Example: GroupName [{{1, 1}, {7, 2}, {2, 3}, {2, 6}}] gives {D6}, GroupName[CaseCount[{ 1,2,2,2,4,4,4,4}]] gives {Z2 x Z4}."; GroupName[Ords_List] := Ordnungen[[1 + Flatten[Position[Ordnungen, Ords]]]]; v[a_, b_, k_, n_] := Mod[a + PowerMod[k, a, n]*b, n]; f[k_, n_] := GroupName[ CaseCount[ ElementOrders[Range[0, n - 1], 0, v[#1, #2, k, n] &, MaxIterations -> 1000]]]; Table[{Map[{"n=" <> ToString[n] <> ", k=" <> ToString[#] <> ": " <> ToString[f[#, n][[1]]] <> " " <> If[Length[f[#, n]] > 1, "*", ""]} &, Select[Range[1, n], ((PowerMod[#, n, n] == 1) && (PowerMod[#, # - 1, n] == 1)) &]]}, {n, 1, 32}] // TableForm