|
|
A318576
|
|
Number of solutions to x^n == 1 (mod n!).
|
|
0
|
|
|
1, 1, 1, 8, 1, 48, 1, 256, 27, 160, 1, 2304, 1, 896, 675, 4096, 1, 20736, 1, 204800, 567, 5632, 1, 5308416, 125, 13312, 2187, 114688, 1, 4147200, 1, 4194304, 29403, 69632, 6125, 286654464, 1, 155648, 9477, 262144000, 1, 585252864, 1, 507510784, 36905625, 753664, 1, 587068342272, 2401, 204800000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
a(n) = 1 iff n = 1 or is prime. For composite n, n and a(n) always have the same prime factors (but not necessarily the same multiplicity).
It appears that a(n) is usually larger for even n. The smallest odd n such that a(n) > a(n+1) is 45; the smallest odd n such that a(n) > a(n-1) is 63; the smallest odd n such that a(n) > a(n+1) and a(n) > a(n-1) is 315.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Product_{p<=n-1} gcd(n, p-1)*p^(v(p, n)) if n odd or n = 2, 4; 2*Product_{p<=n-1} gcd(n, p-1)*p^(v(p, n)) if n even >= 6, where the product is taken over the primes and v(p, n) is the p-adic valuation of n.
|
|
EXAMPLE
|
The solutions to x^4 == 1 (mod 4!) is x == 1, 5, 7, 11, 13, 17, 19, 23 (mod 24), so a(4) = 8.
Note that the multiplicative group of integers modulo 6! = 720 is isomorphic to C_2 X C_2 X C_4 X C_12, so a(6) = gcd(6, 2)*gcd(6, 2)*gcd(6, 4)*gcd(6, 12) = 2*2*2*6 = 48.
|
|
PROG
|
(PARI) a(n)=prod(i=1, primepi(n-1), gcd(n, prime(i)-1)*prime(i)^valuation(n, prime(i)))*(if(n<=4||Mod(n, 2)==1, 1, 2))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|