login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A270120 Number of k with k^n=1 (mod n) and k^k=k (mod n); related to some groups of order n 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

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).

LINKS

Table of n, a(n) for n=1..100.

Alfred Heiligenbrunner, A270120 Further examples and how the small groups were named

OEIS Wiki, OEIS Wiki Groups of order n

EXAMPLE

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

...

MATHEMATICA

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

PROG

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

CROSSREFS

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

Sequence in context: A285707 A164879 A200219 * A009195 A072994 A052126

Adjacent sequences:  A270117 A270118 A270119 * A270121 A270122 A270123

KEYWORD

nonn,easy

AUTHOR

Alfred Heiligenbrunner, Mar 11 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 00:17 EST 2017. Contains 295954 sequences.