A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 8, 3, 2, 1, 8, 5, 2, 9, 4, 1, 4, 1, 16, 1, 2, 1, 12, 1, 2, 3, 16, 1, 12, 1, 4, 3, 2, 1, 16, 7, 10, 1, 8, 1, 18, 5, 8, 3, 2, 1, 16, 1, 2, 9, 32, 1, 4, 1, 8, 1, 4, 1, 24, 1, 2, 5, 4, 1, 12, 1, 32, 27, 2, 1, 24, 1, 2, 1, 8, 1, 12, 1, 4, 3

Offset: 1

Author

Benoit Cloitre, Aug 21 2002

Keywords

• easy
• nonn

Comments

More generally, if the equation a(x)*m=x has solutions, solutions are congruent to m: a(x)*7=x for x=7, 14, 21, 28, 49, 56, 63, 98, 112, ... . There are some composite values of m such that a(x)*m=x has solutions, as m=15. a(n) coincides with A009195(n) at many values of n, but not at n = 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, ... . It seems also that for n large enough sum_{k=1..n} a(k) > n*log(n)*log(log(n)).

Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices. - M. F. Hasler, Feb 23 2014

Links

• T. D. Noe, Table of n, a(n) for n=1..10000

Programs

Maple

1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])),n=2..100); # Robert Israel, Dec 07 2014

Mathematica

f[n_] := (d = If[ OddQ@ n, 1, 2]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = f[2] = 1; Array[f, 93] (* or *)
f[n_] := Length@ Select[ Range@ n, PowerMod[#, n, n] == 1 &]; f[n_] := 1 /; n<2; Array[f, 93] (* Robert G. Wilson v, Dec 06 2014 *)

PARI

A072994=n->sum(k=1,n,Mod(k,n)^n==1) \\ M. F. Hasler, Feb 23 2014

Formula

For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n-1), a(A065119(n)) = A065119(n)/3.

For n>1, a(A026383(n)) = A026383(n)/5.

Extensions

Corrected by T. D. Noe, May 19 2007