A252760 Number of moduli m such that the multiplicative order of n mod m equals n.

0, 1, 2, 4, 9, 10, 12, 72, 112, 33, 12, 212, 42, 22, 108, 96, 35, 456, 6, 1912, 714, 220, 60, 5364, 4032, 747, 448, 3944, 762, 24370, 8, 5376, 738, 8148, 996, 253568, 1143, 242, 980, 46032, 248, 65138, 56, 23004, 195768, 282, 28, 386736, 327520, 12102, 24366

Offset: 1

Author

Alois P. Heinz, Dec 21 2014

Keywords

• nonn

Crossrefs

Main diagonal of A212957.

Cf. A000005, A008683.

Programs

Maple

with(numtheory):
a:= n-> add(mobius(n/d)*tau(n^d-1), d=divisors(n)):
seq(a(n), n=1..30);

Mathematica

a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, n^#-1]&]; a[1] = 0;
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 46}] (* Jean-François Alcover, Mar 25 2017, translated from Maple *)

PARI

a(n) = if (n==1, 1, sumdiv(n, d, moebius(n/d)*numdiv(n^d-1))); \\ Michel Marcus, Mar 25 2017

Formula

a(n) = |{m : multiplicative order of n mod m = n}|.

a(n) = Sum_{d|n} mu(n/d)*tau(n^d-1), mu = A008683, tau = A000005.