A318576 Number of solutions to x^n == 1 (mod n!).

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

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

Table of n, a(n) for n=1..50.

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

Sequence in context: A050401 A333403 A271060 * A089276 A051932 A347489

Adjacent sequences: A318573 A318574 A318575 * A318577 A318578 A318579

Keyword

nonn

Author

Jianing Song, Aug 29 2018

Status

approved