login
Smallest primitive root modulo n, or 0 if no root exists.
25

%I #63 Feb 22 2024 09:46:48

%S 0,0,1,2,3,2,5,3,0,2,3,2,0,2,3,0,0,3,5,2,0,0,7,5,0,2,7,2,0,2,0,3,0,0,

%T 3,0,0,2,3,0,0,6,0,3,0,0,5,5,0,3,3,0,0,2,5,0,0,0,3,2,0,2,3,0,0,0,0,2,

%U 0,0,0,7,0,5,5,0,0,0,0,3,0,2,7,2,0,0,3,0,0,3,0,0,0,0,5,0,0,5,3,0,0

%N Smallest primitive root modulo n, or 0 if no root exists.

%C The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence.

%C a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - _Tom Edgar_, Jun 02 2014

%H T. D. Noe, <a href="/A046145/b046145.txt">Table of n, a(n) for n = 0..10000</a>

%H Pēteris K. Siliņš, <a href="https://fse.studenttheses.ub.rug.nl/31964/">Cross ratios for finite field geometries</a>, Bachelor's Thesis, Univ. Groningen (Netherlands, 2024). See p. 17.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimitiveRoot.html">Primitive Root.</a>

%p A046145 := proc(n)

%p if n <=1 then

%p 0;

%p else

%p pr := numtheory[primroot](n) ;

%p if pr = FAIL then

%p return 0 ;

%p else

%p return pr ;

%p end if;

%p end if;

%p end proc:

%p seq(A046145(n),n=0..110) ; # _R. J. Mathar_, Jul 08 2010

%t smallestPrimitiveRoot[n_ /; n <= 1] = 0; smallestPrimitiveRoot[n_] := Block[{pr = PrimitiveRoot[n], g}, If[! NumericQ[pr], g = 0, g = 1; While[g <= pr, If[ CoprimeQ[g, n] && MultiplicativeOrder[g, n] == EulerPhi[n], Break[]]; g++]]; g]; smallestPrimitiveRoot /@ Range[0, 100] (* _Jean-François Alcover_, Feb 15 2012 *)

%t f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[1]]]]; Array[f, 105, 0] (* v10.0 _Robert G. Wilson v_, Nov 04 2014 *)

%o (PARI) { A046145(n) = for(q=1,n-1, if(gcd(q,n)==1 && znorder(Mod(q,n))==eulerphi(n), return(q);)); 0; } /* _V. Raman_, Nov 22 2012, edited by _Max Alekseyev_, Apr 20 2017 */

%o (Perl) use ntheory ":all"; say "$_ ", znprimroot($_) || 0 for 0..100; # _Dana Jacobsen_, Mar 16 2017

%Y Cf. A001918, A046144, A046146, A002233, A071894, A219027, A008330, A010554, A111076, A285512, A285513, A285514.

%K nonn,easy,nice

%O 0,4

%A _Eric W. Weisstein_

%E Initial terms corrected by _Harry J. Smith_, Jan 27 2005