A318576 - OEIS

%I #6 Aug 30 2018 03:57:03

%S 1,1,1,8,1,48,1,256,27,160,1,2304,1,896,675,4096,1,20736,1,204800,567,

%T 5632,1,5308416,125,13312,2187,114688,1,4147200,1,4194304,29403,69632,

%U 6125,286654464,1,155648,9477,262144000,1,585252864,1,507510784,36905625,753664,1,587068342272,2401,204800000

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

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

%C 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.

%F 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.

%e The solutions to x^4 == 1 (mod 4!) is x == 1, 5, 7, 11, 13, 17, 19, 23 (mod 24), so a(4) = 8.

%e 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.

%o (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))

%K nonn

%O 1,4

%A _Jianing Song_, Aug 29 2018