A317993 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

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) = my(i=0, search_max = A057635(eulerphi(n))); for(j=eulerphi(n), 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; modified on Jan 11 2026

(PARI) A317993(n) = #select(x->znstar(x)[2]==znstar(n)[2], invphi(eulerphi(n))) \\ Jianing Song, Jan 11 2026 using Max Alekseyev's invphi.gp

CROSSREFS

Cf. A015126, A028476, A057635.

Earliest occurrence of m is A303712(m).

Sequence in context: A179751 A373888 A039645 * A048687 A308621 A308623

Adjacent sequences: A317990 A317991 A317992 * A317994 A317995 A317996

KEYWORD

nonn

AUTHOR

Jianing Song, Oct 03 2018

STATUS

approved