A389781 Number of divisors d of n such that d^(n/d) == d (mod n).

1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 3, 2, 4, 4, 2, 2, 3, 2, 4, 4, 4, 2, 3, 2, 4, 2, 3, 2, 5, 2, 2, 4, 4, 4, 3, 2, 4, 4, 3, 2, 6, 2, 3, 3, 4, 2, 3, 2, 3, 4, 4, 2, 3, 4, 3, 4, 4, 2, 5, 2, 4, 3, 2, 4, 5, 2, 4, 4, 5, 2, 4, 2, 4, 3, 3, 4, 6, 2, 3, 2, 4, 2, 5, 4, 4, 4, 3, 2, 5, 4, 3, 4, 4, 4, 3

Offset

1,2

Comments

a(n) is the number of unique pairs of coprime x,y satisfying x*y = n and y^(x - 1) == 1 (mod x). Note that x and y are symmetric in the congruence. - Aloe Poliszuk, Oct 20 2025

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Formula

From Aloe Poliszuk, Oct 20 2025: (Start)

a(p^e) = 2.

a(n) <= 2^(omega(n)), where omega = A001221. (End)

Mathematica

a[n_]:=Module[{d=Divisors[n]}, Count[PowerMod[d, n/d, n]-Mod[d, n], 0]]; Array[a, 96] (* James C. McMahon, Oct 25 2025 *)

Prog

(Magma) [1 + #[d: d in [1..n-1] | n mod d eq 0 and Modexp(d, n div d, n) eq d]: n in [1..90]];
(PARI) a(n) = sumdiv(n, d, lift(Mod(d, n)^(n/d)) == d%n); \\ Aloe Poliszuk, Oct 20 2025

Crossrefs

Cf. A000005, A384237.

Sequence in context: A384834 A391684 A232398 * A048669 A365499 A383762

Adjacent sequences: A389778 A389779 A389780 * A389782 A389783 A389784

Keyword

nonn

Author

Juri-Stepan Gerasimov, Oct 14 2025

Status

approved