cp's OEIS Frontend

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

%I A317993 #22 May 12 2024 18:11:21
%S A317993 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 A317993 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 A317993 3,7,2,3,2,2,5,4,7,7,2,1,2,2,2,3,2,4,3
%N A317993 Number of k such that (Z/kZ)* is isomorphic to (Z/nZ)*, where (Z/nZ)* is the multiplicative group of integers modulo n.
%C A317993 To find solutions for k to (Z/kZ)* = (Z/nZ)*, it's sufficient to check for A015126(n) <= k <= A028476(n).
%C A317993 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 A317993 Conjecture: Every number occurs in this sequence.
%H A317993 Jianing Song, <a href="/A317993/b317993.txt">Table of n, a(n) for n = 1..20000</a>
%H A317993 Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%e A317993 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 A317993 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 A317993 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 A317993 (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 A317993 Cf. A015126, A028476, A057635.
%Y A317993 Earliest occurrence of m is A303712(m).
%K A317993 nonn
%O A317993 1,1
%A A317993 _Jianing Song_, Oct 03 2018