|
%I #101 Feb 02 2020 07:54:55
%S 1,2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31,34,37,38,
%T 41,43,46,47,49,50,53,54,58,59,61,62,67,71,73,74,79,81,82,83,86,89,94,
%U 97,98,101,103,106,107,109,113,118,121,122,125,127,131,134,137,139
%N Numbers that have a primitive root (the multiplicative group modulo n is cyclic).
%C The sequence consists of 1, 2, 4 and numbers of the form p^i and 2p^i, where p is an odd prime and i >= 1.
%C Sequence gives values of n such that x^2 == 1 (mod n) has no solution with 1 < x < n-1. - _Benoit Cloitre_, Jan 04 2002
%C Gaussian criterion for terms of the sequence: n is in the sequence iff Product_{1<=i<=n-1, gcd(i,n)=1} i == -1 (mod n), see example. - _Vladimir Shevelev_, Jan 11 2011
%C For the criterion used above see the Hardy and Wright reference, Theorem 129. p. 102, a consequence of Bauer's theorem. See also _T. D. Noe_'s comment with the Nagell reference on A060594 and also A160377. - _Wolfdieter Lang_, Feb 16 2012
%C Also numbers n such that phi(n) = lambda(n) (or numbers with A034380(n)=1), where phi is A000010, and lambda is Carmichael's lambda: A002322. - _Enrique Pérez Herrero_, Jun 04 2013
%C All values of n>2 are given when there are exactly two solutions for n*j+1 is a square, 0 <= j < n, which are j = {0, n-2}. See Mathematica examples. - _Richard R. Forberg_, Mar 26 2016
%C Numbers n such that the Galois group of the cyclotomic field with the n-th roots of unity is a cyclic group. [Van der Waerden, p. 55, Th. 4.11.; Corwin, 1967] - _N. J. A. Sloane_, Nov 26 2016
%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.
%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.
%D B. L. van der Waerden, Modern Algebra, 2nd. ed., Ungar, NY, Vol. I, 1948.
%H T. D. Noe, <a href="/A033948/b033948.txt">Table of n, a(n) for n = 1..10000</a>
%H Anonymous, <a href="http://ihome.cuhk.edu.hk/~s005636/number/primitive.pdf">Notes on Number Theory:Primitive Roots</a> [broken link]
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 778.
%H L. J. Corwin, <a href="/A033948/a033948.pdf">Irreducible polynomials over the integers which factor mod p for every p</a>, Unpublished Bell Labs Memo, Sep 07 1967 [Annotated scanned copy]
%H Math Reference Project, <a href="http://www.mathreference.com/num-mod,proot.html">Primitive Root</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimitiveRoot.html">Primitive Root</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group</a>
%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/31/10/ShowAll.html">Prime Roots</a>
%e Gaussian product for n=9 is 1*2*4*5*7*8=2240. Since 2240==-1(mod 9), then 9 is in the sequence. - _Vladimir Shevelev_, Jan 11 2011
%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..139]); # _Peter Luschny_, May 25 2017
%t Join[{1}, Select[ Range[140], IntegerQ[ PrimitiveRoot[#]] &]] (* _Jean-François Alcover_, Sep 27 2011 *)
%t Select[Range[139], EulerPhi[#] == CarmichaelLambda[#] &] (* _T. D. Noe_, Jun 04 2013 *)
%t result = {}; Do[count = 0;
%t Do[If[Mod[j^2, n] == 1, count++], {j, 2, n - 2}];
%t If[count == 0, AppendTo[result, n]], {n, 1, 200}]; result (* _Richard R. Forberg_, Mar 26 2016 *)
%t result = {}; Do[count = 0;
%t Do[ r = Sqrt[n*j + 1]; If[IntegerQ[r], count++], {j, 0, n}];
%t If[count == 2, AppendTo[result, n]], {n, 0, 200}]; result (* missing{1,2} _Richard R. Forberg_, Mar 26 2016 *)
%o (PARI) is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2,&n) && n>2)) \\ _Charles R Greathouse IV_, Apr 16 2015
%Y Cf. A033949 (complement), A072209, A001783 (Gaussian products used in the V. Shevelev example).
%Y Cf. also A002322, A060594, A062373, A034380, A160377.
%Y Union of 1, 2, 4, A061345, A278568.
%K nonn
%O 1,2
%A Calculated by _Jud McCranie_, entered by _N. J. A. Sloane_
|
