A333387 Number of solutions to x^y == 1 (mod n) where 0 <= x < n and 1 <= y <= n.

1, 2, 4, 6, 9, 9, 16, 20, 21, 19, 28, 30, 41, 33, 48, 56, 49, 45, 64, 70, 83, 57, 64, 108, 85, 83, 90, 112, 105, 103, 136, 144, 141, 99, 186, 150, 169, 129, 218, 260, 181, 175, 196, 190, 251, 129, 136, 312, 217, 175, 270, 296, 201, 189, 324, 414, 323, 211, 172

Offset

1,2

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(2^k) = (2*k-1)*2^(k-1) for k >= 1.

If n possesses a primitive root (i.e., n is in A033948), then a(n) = Sum_{k=1..n} gcd(phi(n),k), where phi is Euler's totient function A000010.

From Ridouane Oudra, May 28 2026: (Start)

a(n) = Sum_{1<=k<=n, gcd(n,k)=1} floor(n/order(k,n)).

a(n) = Sum_{d|lambda(n)} floor(n/d)*A252911(n,d), where lambda = A002322.

If n is in A033948 then:

a(n) = Sum_{d|lambda(n)} phi(d)*floor(n/d), or also: a(n) = Sum_{d|phi(n)} phi(d)*floor(n/d).

In particular, a(p) = Sum_{d|(p-1)} phi(d)*floor(p/d), for p prime. (End)

Example

a(3) = 4 because there are 4 solutions to x^y == 1 (mod 3): 1^1 == 1 (3), 1^2 == 1 (3), 1^3 == 1 (3), 2^2 == 1 (3).

Maple

f:= proc(n) local t, x, r;
  t:= 0;
  for x from 1 to n-1 do  if igcd(n, x) = 1 then
    r:= numtheory:-order(x, n);
    t:= t + floor(n/r)
  fi od;
  t
end proc:
f(1):= 1:
map(f, [$1..100]): # Robert Israel, Mar 25 2020

Mathematica

a[n_] := If[n == 1, 1, Sum[Boole[PowerMod[x, y, n] == 1], {x, 0, n - 1}, {y, 1, n}]];
Array[a, 100] (* Jean-François Alcover, Jun 08 2020 *)

Prog

(PARI) a(n) = sum(x=0, n-1, sum (y=1, n, Mod(x, n)^y == 1)); \\ Michel Marcus, Mar 20 2020

Crossrefs

Cf. A333386, A333388, A033948, A252911, A000010, A002322.

Sequence in context: A377255 A084407 A114526 * A178126 A359515 A162202

Adjacent sequences: A333384 A333385 A333386 * A333388 A333389 A333390

Keyword

nonn

Author

Franz Vrabec, Mar 18 2020

Extensions

More terms from Hugo Pfoertner, Mar 22 2020

Status

approved