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

Author

Jianing Song, Oct 03 2018

Keywords

• nonn

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.

Examples

			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.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..20000
• Wikipedia, Multiplicative group of integers modulo n

Crossrefs

Cf. A015126, A028476, A057635.

Earliest occurrence of m is A303712(m).

Programs

PARI

a(n) = if(abs(n)==1||abs(n)==2, 2, my(i=0, search_max = A057635(eulerphi(n))); for(j=eulerphi(n)+1, search_max, if(znstar(j)[2]==znstar(n)[2], i++)); i) \\ search_max is the largest k such that phi(k) = phi(n). See A057635 for its program