A270120 Number of k with k^n=1 (mod n) and k^k=k (mod n); related to some groups of order n.

0, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 6, 1, 4, 1, 6, 3, 2, 1, 8, 5, 2, 3, 4, 1, 4, 1, 6, 1, 2, 1, 8, 1, 2, 3, 12, 1, 8, 1, 4, 3, 2, 1, 12, 7, 6, 1, 6, 1, 4, 5, 8, 3, 2, 1, 12, 1, 2, 9, 10, 1, 4, 1, 6, 1, 4, 1, 16, 1, 2, 5, 4, 1, 8, 1, 20, 9, 2, 1, 16, 1, 2, 1, 8, 1, 8, 1, 4, 3, 2, 1, 12, 1, 8, 3, 14

Offset: 1

Author

Alfred Heiligenbrunner, Mar 11 2016

Keywords

• nonn
• easy

Comments

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.

a(n) gives the number of different k out of {1, 2, ..., n-1} that comply the conditions.

E.g., for n = 4, k = -1 (or, what is the same, k = 3) results in the Klein four-group. (a o_3 b := a + (-1)^a * b (mod 4).)

Note that different k can result in groups that are isomorphic to each other.

The neutral element is always 0.

The inverse element to a is always -a*k^(-a) (mod n).

Examples

			a(4) = 2, because in Z_4, k == 1 and k == 3 are the only number out of {0, 1, 2, 3} with conditions k^k==k mod n and k^n==1 mod n.
a(8) = 4, because k can be out of {1, 3, 5, 7}.
a(18) = 4, because k can be out of {1, 7, 13, 17}.
If n is even, k == -1 (or, equivalently, k == n-1) is always to be counted. This group is isomorphic to the Dihedral group D_(n/2), with generating elements -1 and 2.
The following table shows the first results with n, k and the name of the group (due to A. D. Thomas and G. V. Wood: 'Group Tables', found by comparing the element-orders).
Note that for n=8, k=1 and k=5 result in Z8. None of the k results in Z2 x Z4 or in Z2 x Z2 x Z2.
Note that for n=9 all k are isomorphic to Z9, none to Z3 x Z3.
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
...
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Alfred Heiligenbrunner, A270120 Further examples and how the small groups were named
• OEIS Wiki, OEIS Wiki Groups of order n

Crossrefs

Cf. A000001 (number of groups of order n).

Programs

Mathematica

Table[Length[ Select[Range[1, n-1], ((GCD[n, # - 1] > 1) && (PowerMod[#, n, n] == 1) && (PowerMod[#, # - 1, n] == 1)) &]], {n, 1, 100}]

PARI

a(n) = sum(k=1, n-1, (Mod(k,n)^n == 1) && (Mod(k,n)^k == k)); \\ Michel Marcus, Mar 12 2016