A317993 Number of k such that (Z/kZ)* is isomorphic to (Z/nZ)*, where (Z/nZ)* is the multiplicative group of integers modulo n.

2, 2, 3, 3, 2, 3, 4, 2, 4, 2, 2, 2, 2, 4, 4, 4, 2, 4, 4, 4, 4, 2, 2, 1, 2, 2, 4, 4, 2, 4, 2, 1, 3, 2, 7, 4, 2, 4, 7, 3, 2, 4, 4, 3, 7, 2, 2, 3, 4, 2, 4, 7, 2, 4, 5, 3, 4, 2, 2, 3, 2, 2, 2, 4, 2, 3, 2, 4, 3, 7, 2, 3, 2, 2, 5, 4, 7, 7, 2, 1, 2, 2, 2, 3, 2, 4, 3

Offset

1,1

Comments

To find solutions for k to (Z/kZ)* = (Z/nZ)*, it's sufficient to check for A015126(n) <= k <= A028476(n).

It seems that this sequence is unbounded. For example, there are 59 solutions to (Z/nZ)* = C_2 X C_6 X C_1260.

Conjecture: every number occurs in this sequence.

Links

Jianing Song, Table of n, a(n) for n = 1..20000

Wikipedia, Multiplicative group of integers modulo n

Example

The solutions to (Z/kZ)* = C_6 are k = 7, 9, 14 and 18, so a(7) = a(9) = a(14) = a(18) = 4.
The solutions to (Z/kZ)* = C_2 X C_20 are k = 55, 75, 100, 110 and 150, so a(55) = a(75) = a(100) = a(110) = a(150) = 5.
The solutions to (Z/kZ)* = C_2 X C_12 are k = 35, 39, 45, 52, 70, 78 and 90, so a(35) = a(39) = a(45) = a(52) = a(70) = a(78) = a(90) = 7.

Prog

(PARI) a(n) = if(abs(n)==1||abs(n)==2, 2, my(i=0, k=eulerphi(n)); for(j=k+1, 3*k*log(log(k))+16, if(znstar(j)[2]==znstar(n)[2], i++)); i)

Crossrefs

Cf. A015126, A028476.

Earliest occurrence of m is A303712(m).

Sequence in context: A023514 A179751 A039645 * A048687 A308621 A308623

Adjacent sequences: A317990 A317991 A317992 * A317994 A317995 A317996

Keyword

nonn

Author

Jianing Song, Oct 03 2018

Status

approved