OFFSET
1,1
COMMENTS
Number of bases b, 1 <= b <= 2*n, such that GCD(b, 2*n+1) = 1 and b^n == (b / 2*n+1) (mod 2*n+1), where (b / 2*n+1) is a Jacobi symbol.
If 2*n+1 is composite then it is the number of bases b, 1 <= b <= 2*n, in which 2*n+1 is an Euler-Jacobi pseudoprime.
Differs from A071294 from n = 22.
REFERENCES
Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 96.
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10000
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Wikipedia, Euler-Jacobi pseudoprime.
Wikipedia, Solovay-Strassen primality test.
FORMULA
a(n) = delta(n) * Product_{p|n} gcd((n-1)/2, p-1), where delta(n) = 2 if nu(n-1, 2) = min_{p|n} nu(p-1, 2), 1/2 if there is a prime p|n such that nu(p, n) is odd and nu(p-1, 2) < nu(n-1, 2), and 1 otherwise, where nu(n, p) is the exponent of the highest power of p dividing n.
a(p) = p-1 for prime p.
EXAMPLE
a(1) = 2 since there are 2 bases b in which 2*1 + 1 = 3 is an Euler-Jacobi pseudoprime: b = 1 since GCD(1, 3) = 1 and 1^1 == (1 / 3) == 1 (mod 3), and b = 2 since GCD(2, 3) = 1 and 2^1 == (2 / 3) == -1 (mod 3).
MATHEMATICA
v[n_] := Min[IntegerExponent[#, 2]& /@ (FactorInteger[n][[;; , 1]] - 1)];
pQ[n_, p_] := OddQ[IntegerExponent[n, p]] && IntegerExponent[p-1, 2] < IntegerExponent[n-1, 2];
psQ[n_] := AnyTrue[FactorInteger[n][[;; , 1]], pQ[n, #] &];
delta[n_] := If[IntegerExponent[n-1, 2] == v[n], 2, If[psQ[n], 1/2, 1]];
a[n_] := delta[n] * Module[{p = FactorInteger[n][[;; , 1]]}, Product[GCD[(n-1)/2, p[[k]]-1], {k, 1, Length[p]}]];
Table[a[n], {n, 3, 147, 2}]
KEYWORD
nonn
AUTHOR
Amiram Eldar, Nov 20 2019
STATUS
approved