login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #22 May 12 2024 18:11:21

%S 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,

%T 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,

%U 3,7,2,3,2,2,5,4,7,7,2,1,2,2,2,3,2,4,3

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

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

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

%C Conjecture: Every number occurs in this sequence.

%H Jianing Song, <a href="/A317993/b317993.txt">Table of n, a(n) for n = 1..20000</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>

%e The solutions to (Z/kZ)* = C_6 are k = 7, 9, 14 and 18, so a(7) = a(9) = a(14) = a(18) = 4.

%e 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.

%e 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.

%o (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

%Y Cf. A015126, A028476, A057635.

%Y Earliest occurrence of m is A303712(m).

%K nonn

%O 1,1

%A _Jianing Song_, Oct 03 2018