A272831 Number of distinct multiplicative groups mod n having 1 as the identity element.

0, 1, 2, 2, 3, 2, 4, 5, 4, 3, 4, 5, 6, 4, 8, 8, 5, 4, 6, 8, 10, 4, 4, 16, 6, 6, 6, 10, 6, 8, 8, 11, 10, 5, 16, 10, 9, 6, 16, 27, 8, 10, 8, 10, 16, 4, 4, 27, 8, 6, 14, 16, 6, 6, 16, 32, 15, 6, 4, 27, 12, 8, 30, 14, 30, 10, 8, 14, 10, 16, 8, 32, 12, 9, 16, 15

Offset

1,3

Comments

Trivial upper bound: a(n) <= 2^(phi(n)-1). - Charles R Greathouse IV, Jun 08 2016

Equivalently, the number of subgroups of the multiplicative group of integers modulo n. - Andrew Howroyd, Jul 01 2018

Also a(n) is the number of subfields of the n-th cyclotomic field Q(exp(2*Pi*i/n)). - Jianing Song, Feb 12 2021

Links

Keith F. Lynch, Table of n, a(n) for n = 1..1000

ResearchGate, How many subfields does a cyclotomic field have

Example

For instance a(30) = 8 because only the following 8 groups exist: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29}.

Prog

(GAP) Concatenation([0], List([2..80], n->Sum( ConjugacyClassesSubgroups( LatticeSubgroups( GL(1, ZmodnZ(n)))), Size))); # Andrew Howroyd, Jul 01 2018

Crossrefs

For any identity element, not just 1, see A281365.

Cf. A272213.

Sequence in context: A342297 A305820 A364934 * A290076 A289626 A097004

Adjacent sequences: A272828 A272829 A272830 * A272832 A272833 A272834

Keyword

nonn

Author

Keith F. Lynch, May 07 2016

Status

approved