OFFSET
1,5
COMMENTS
Old name was: "Number of primitive solutions of system "for all 2<=i<=n, k^i > 1 mod n"."
The meaning of "primitive" is twofold: (i) Because k^i == (k+n)^i (mod n), we admit only solutions k where k is the representative 2<=k<n. (ii) For prime n, the residue k^i==1 (mod n) is unavoidable if we let i run through the numbers counted by phi(n). So we also admit solutions k where the set of {k^i mod n} is the full {1,2,...,n-1}. - R. J. Mathar, Robert Israel, Jun 09 2016
If n is an odd prime, a(n) = A000010(n-1). If n is composite, a(n) = n-n(1+A173557(n))/A007947(n). - Robert Israel, Jun 09 2016
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000
MAPLE
A027413 := proc(n)
local a, k, i, kimods ;
a := 0 ;
for k from 2 to n-1 do
kimods := {} ;
for i from 2 to n do
kimods := kimods union {modp(k^i, n)};
end do:
if min(op(kimods)) > 1 or nops(kimods) = n-1 then
a := a+1 ;
end if;
end do:
a ;
end proc: # R. J. Mathar, Jun 09 2016
f:= proc(n)
local F, q, r;
if isprime(n) then numtheory:-phi(n-1)
else
F:= numtheory:-factorset(n);
q:= convert(F, `*`);
r:= convert(map(`-`, F, 1), `*`);
n*(q-r-1)/q;
fi;
end proc:
f(2):= 0: f(1):= 0:
map(f, [$1..1000]); # Robert Israel, Jun 09 2016
MATHEMATICA
f[n_] := Module[{F, q, r}, If[PrimeQ[n], EulerPhi[n-1], F = FactorInteger[ n][[All, 1]]; q = Times @@ F; r = Times @@ (F-1); n(q-r-1)/q]];
f[2] = 0; f[1] = 0;
f /@ Range[100] (* Jean-François Alcover, Aug 15 2020, after Robert Israel *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Sandor Adrian (sandor(AT)skylab.math.unibuc.ro), Olivier Gérard
EXTENSIONS
Better definition from Robert Israel, Jun 09 2016
STATUS
approved