login
Number of primitive roots g mod prime(n) for which there is no solution to g^x == x (mod p) with 2 <= x <= prime(n)-2.
1

%I #15 Oct 12 2020 11:14:27

%S 1,1,1,1,2,1,1,3,4,2,1,6,5,2,9,11,12,5,7,9,8,8,17,12,11,16,12,23,20,

%T 16,17,17,23,17,26,18,19,25,26,32,38,21,21,18,27,25,24,27,52,30,44,33,

%U 19,44,54,45,57,14,29,27,39,58,28,41,39,62,26,25,69,48,51,61,44,47,37,63,77,55,55,41

%N Number of primitive roots g mod prime(n) for which there is no solution to g^x == x (mod p) with 2 <= x <= prime(n)-2.

%H Robert Israel, <a href="/A286510/b286510.txt">Table of n, a(n) for n = 1..1000</a>

%H M. Levin, C. Pomerance, K. Soundararajan, <a href="https://doi.org/10.1007/978-3-642-14518-6_5">Fixed Points for Discrete Logarithms</a>. In: Hanrot G., Morain F., Thomé E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg (2010).

%H Math Overflow, <a href="https://mathoverflow.net/q/269368">Fixed points of g^x (modulo a prime)</a>

%F a(n) = A008330(n) - A174407(n) for n >= 2.

%p f:= proc(n) local p, r, S, R,x;

%p p:= ithprime(n);

%p r:= numtheory:-primroot(p);

%p S:= select(t -> igcd(t,p-1) = 1, {$1..p-1});

%p R:= map(s -> r &^ s mod p, S);

%p for x from 2 to p-2 do

%p R:= remove(t -> (t &^ x - x mod p = 0), R);

%p od;

%p nops(R);

%p end proc;

%p map(f, [$1..100]);

%t Join[{1}, Table[p = Prime[n]; EulerPhi[EulerPhi[p]] - Length[Select[ PrimitiveRootList[p], MemberQ[PowerMod[#, Range[p-1], p] - Range[p-1], 0] &]], {n, 2, 100}]] (* _Jean-François Alcover_, Oct 11 2020, after _T. D. Noe_ in A174407 *)

%Y Cf. A008330, A174407.

%K nonn

%O 1,5

%A _Robert Israel_, May 10 2017