cp's OEIS Frontend

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

%I A046145 #64 Feb 16 2025 08:32:38
%S A046145 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 A046145 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 A046145 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 A046145 Smallest primitive root modulo n, or 0 if no root exists.
%C A046145 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 A046145 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 A046145 T. D. Noe, <a href="/A046145/b046145.txt">Table of n, a(n) for n = 0..10000</a>
%H A046145 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 A046145 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimitiveRoot.html">Primitive Root.</a>
%p A046145 A046145 := proc(n)
%p A046145   if n <=1 then
%p A046145     0;
%p A046145   else
%p A046145     pr := numtheory[primroot](n) ;
%p A046145     if pr = FAIL then
%p A046145        return 0 ;
%p A046145     else
%p A046145        return pr ;
%p A046145     end if;
%p A046145   end if;
%p A046145 end proc:
%p A046145 seq(A046145(n),n=0..110) ;  # _R. J. Mathar_, Jul 08 2010
%t A046145 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 A046145 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 A046145 (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 A046145 (Perl) use ntheory ":all"; say "$_ ", znprimroot($_) || 0  for 0..100; # _Dana Jacobsen_, Mar 16 2017
%Y A046145 Cf. A001918, A046144, A046146, A002233, A071894, A219027, A008330, A010554, A111076, A285512, A285513, A285514.
%K A046145 nonn,easy,nice
%O A046145 0,4
%A A046145 _Eric W. Weisstein_
%E A046145 Initial terms corrected by _Harry J. Smith_, Jan 27 2005