A354057 Square array read by ascending antidiagonals: T(n,k) is the number of solutions to x^k == 1 (mod n).

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 4, 3, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 3, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 6, 1, 4, 1, 2, 1, 1, 1, 4, 1, 4, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Author

Jianing Song, May 16 2022

Keywords

• nonn
• tabl

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

Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354060.

Each column is multiplicative.

Examples

			  n/k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  10   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
  11   1  2  1  2  5  2  1  2  1 10  1  2  1  2  5  2  1  2  1 10
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  3  4  1  6  1  4  3  2  1 12  1  2  3  4  1  6  1  4
  14   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  15   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  16   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  17   1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 16  1  2  1  4
  18   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  19   1  2  3  2  1  6  1  2  9  2  1  6  1  2  3  2  1 18  1  2
  20   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
		

Links

• Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)

Crossrefs

k-th column: A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).

Applying Moebius transform to the rows gives A354059.

Applying Moebius transform to the columns gives A354058.

Cf. A327924.

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.

A327924(n,k) = Sum_{q|n} T(n,k) * (Sum_{s|n/q} mu(s)/phi(s*q)).