A354060 - OEIS

%I #13 May 22 2022 00:00:17

%S 1,1,1,2,1,2,1,2,1,4,1,2,1,2,3,2,1,6,1,4,1,2,3,2,1,6,1,2,1,4,1,2,1,2,

%T 5,2,1,2,1,10,1,4,1,2,3,4,1,6,1,4,3,2,1,12,1,2,3,2,1,6,1,4,1,8,1,4,1,

%U 8,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16

%N Irregular table read by rows: T(n,k) is the number of solutions to x^k == 1 (mod n), 1 <= k <= psi(n), psi = A002322.

%C Row n and Row n' are the same if and only if (Z/nZ)* = (Z/n'Z)*, where (Z/nZ)* is the multiplicative group of integers modulo m.

%C Given n, T(n,k) only depends on gcd(k,psi(n)).

%H Jianing Song, <a href="/A354060/b354060.txt">Table of n, a(n) for n = 1..8346</a> (the first 200 rows)

%F If (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then T(n,k) = Product_{i=1..r} gcd(k,k_r).

%F T(p^e,k) = gcd((p-1)*p^(e-1),k) for odd primes p. T(2,k) = 1, T(2^e,k) = 2*gcd(2^(e-2),k) if k is even and 1 if k is odd.

%e Table starts

%e n = 1: 1;

%e n = 2: 1;

%e n = 3: 1, 2;

%e n = 4: 1, 2;

%e n = 5: 1, 2, 1, 4;

%e n = 6: 1, 2;

%e n = 7: 1, 2, 3, 2, 1, 6;

%e n = 8: 1, 4;

%e n = 9: 1, 2, 3, 2, 1, 6;

%e n = 10: 1, 2, 1, 4;

%e n = 11: 1, 2, 1, 2, 5, 2, 1, 2, 1, 10;

%e n = 12: 1, 4;

%e n = 13: 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12;

%e n = 14: 1, 2, 3, 2, 1, 6;

%e n = 15: 1, 4, 1, 8;

%e n = 16: 1, 4, 1, 8;

%e n = 17: 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16;

%e n = 18: 1, 2, 3, 2, 1, 6;

%e n = 19: 1, 2, 3, 2, 1, 6, 1, 2, 9, 2, 1, 6, 1, 2, 3, 2, 1, 18;

%e n = 20: 1, 4, 1, 8;

%e ...

%o (PARI) T(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]))

%Y Cf. A354057, A002322, A354061.

%K nonn,tabf

%O 1,4

%A _Jianing Song_, May 16 2022