

A033949


Positive integers that do not have a primitive root.


17



8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 95, 96, 99, 100, 102, 104, 105, 108, 110, 111, 112, 114, 115, 116, 117, 119, 120, 123
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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
The multiplicative group modulo n is noncyclic. See the complement A033948.  Wolfdieter Lang, Mar 14 2012
Numbers n with the property that there exists a natural number m with 1<m<n1 and m^2 == 1 mod n.  Reinhard Muehlfeld, May 27 2014
Also, numbers n for which A000010(n)>A002322(n), or equivalently A034380(n)>1.  Ivan Neretin, Mar 28 2015


REFERENCES

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


LINKS

T. D. Noe, Table of n, a(n) for n=1..10000
Brett A. Harrison, On the reducibility of cyclotomic polynomials over finite fields, Amer. Math. Monthly, Vol 114, No. 9 (2007), 813818


FORMULA

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.


MATHEMATICA

Select[Range[2, 130], !IntegerQ[PrimitiveRoot[#]]&] (* Harvey P. Dale, Oct 25 2011 *)


PROG

(Sage) print [n for n in range(1, 100) if not Integers(n).multiplicative_group_is_cyclic()] # Ralf Stephan, Mar 30 2014
(Haskell)
a033949 n = a033949_list !! (n1)
a033949_list = filter
(\x > any ((== 1) . (`mod` x) . (^ 2)) [2 .. x2]) [1..]
 Reinhard Zumkeller, Dec 10 2014


CROSSREFS

Cf. A033948.
Sequence in context: A032455 A050275 * A175594 A062373 A180690 A194592
Adjacent sequences: A033946 A033947 A033948 * A033950 A033951 A033952


KEYWORD

nonn,changed


AUTHOR

Calculated by Jud McCranie


STATUS

approved



