This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033949 Positive integers that do not have a primitive root. 35


%S 8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,42,44,45,48,51,52,55,56,

%T 57,60,63,64,65,66,68,69,70,72,75,76,77,78,80,84,85,87,88,90,91,92,93,

%U 95,96,99,100,102,104,105,108,110,111,112,114,115,116,117,119,120,123

%N Positive integers that do not have a primitive root.

%C Numbers n such that the cyclotomic polynomial Phi(n,x) is reducible over Zp for all primes p. Harrison shows that this is equivalent to n>2 and the discriminant of Phi(n,x), A004124(n), being a square. - _T. D. Noe_, Nov 06 2007

%C The multiplicative group modulo n is non-cyclic. See the complement A033948. - _Wolfdieter Lang_, Mar 14 2012. See A281854 for the groups. - _Wolfdieter Lang_, Feb 04 2017

%C Numbers n with the property that there exists a natural number m with 1<m<n-1 and m^2 == 1 mod n. - _Reinhard Muehlfeld_, May 27 2014

%C Also, numbers n for which A000010(n)>A002322(n), or equivalently A034380(n)>1. - _Ivan Neretin_, Mar 28 2015

%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.

%H T. D. Noe, <a href="/A033949/b033949.txt">Table of n, a(n) for n = 1..10000</a>

%H Brett A. Harrison, <a href="http://www.jstor.org/stable/27642336">On the reducibility of cyclotomic polynomials over finite fields</a>, Amer. Math. Monthly, Vol 114, No. 9 (2007), 813-818

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Primitive_root_modulo_n">Primitive root modulo n</a>

%F Positive integers except 1, 2, 4 and numbers of the form p^i and 2p^i, where p is an odd prime and i >= 1.

%p m := proc(n) local k, r; r := 1; if n = 2 then return false fi;

%p for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:

%p select(n -> m(n) = 1, [$1..123]); # _Peter Luschny_, May 25 2017

%t Select[Range[2,130],!IntegerQ[PrimitiveRoot[#]]&] (* _Harvey P. Dale_, Oct 25 2011 *)

%t a[n_] := Module[{j, l = {}}, While[Length[l]<n, For[j = 1+If[l=={}, 0, l // Last], True, j++, If[EulerPhi[j] > CarmichaelLambda[j], AppendTo[l, j]; Break[]]]]; l[[n]]]; Array[a, 100] (* _Jean-François Alcover_, May 29 2018, after _Alois P. Heinz_'s Maple code for A277915 *)

%o (Sage) print [n for n in range(1,100) if not Integers(n).multiplicative_group_is_cyclic()] # _Ralf Stephan_, Mar 30 2014

%o (Haskell)

%o a033949 n = a033949_list !! (n-1)

%o a033949_list = filter

%o (\x -> any ((== 1) . (`mod` x) . (^ 2)) [2 .. x-2]) [1..]

%o -- _Reinhard Zumkeller_, Dec 10 2014

%o (PARI) is(n)=n>7 && (!isprimepower(if(n%2,n,n/2)) || n>>valuation(n,2)==1) \\ _Charles R Greathouse IV_, Oct 08 2016

%Y Cf. A033948, A193305 (composites with primitive root).

%Y Column k=1 of A277915, A281854.

%K nonn

%O 1,1

%A Calculated by _Jud McCranie_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 10 20:23 EST 2019. Contains 329909 sequences. (Running on oeis4.)