A354060 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.

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, 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, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16

Offset: 1

Author

Jianing Song, May 16 2022

Keywords

• nonn
• tabf

Comments

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.

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

Examples

			Table starts
n = 1: 1;
n = 2: 1;
n = 3: 1, 2;
n = 4: 1, 2;
n = 5: 1, 2, 1, 4;
n = 6: 1, 2;
n = 7: 1, 2, 3, 2, 1, 6;
n = 8: 1, 4;
n = 9: 1, 2, 3, 2, 1, 6;
n = 10: 1, 2, 1, 4;
n = 11: 1, 2, 1, 2, 5, 2, 1, 2, 1, 10;
n = 12: 1, 4;
n = 13: 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12;
n = 14: 1, 2, 3, 2, 1, 6;
n = 15: 1, 4, 1, 8;
n = 16: 1, 4, 1, 8;
n = 17: 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16;
n = 18: 1, 2, 3, 2, 1, 6;
n = 19: 1, 2, 3, 2, 1, 6, 1, 2, 9, 2, 1, 6, 1, 2, 3, 2, 1, 18;
n = 20: 1, 4, 1, 8;
...
		

Links

• Jianing Song, Table of n, a(n) for n = 1..8346 (the first 200 rows)

Crossrefs

Cf. A354057, A002322, A354061.

Programs

PARI

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

Formula

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).

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.