|
|
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.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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)).
|
|
LINKS
|
|
|
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.
|
|
EXAMPLE
|
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;
...
|
|
PROG
|
(PARI) T(n, k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|