cp's OEIS Frontend

A003277 Cyclic numbers: k such that k and phi(k) are relatively prime; also k such that there is just one group of order k, i.e., A000001(k) = 1.

%I A003277 M0650 #175 Aug 15 2025 10:28:24
%S A003277 1,2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53,59,61,65,
%T A003277 67,69,71,73,77,79,83,85,87,89,91,95,97,101,103,107,109,113,115,119,
%U A003277 123,127,131,133,137,139,141,143,145,149,151,157,159,161,163,167,173
%N A003277 Cyclic numbers: k such that k and phi(k) are relatively prime; also k such that there is just one group of order k, i.e., A000001(k) = 1.
%C A003277 Except for a(2)=2, all the terms in the sequence are odd. This is because of the existence of a non-cyclic dihedral group of order 2n for each n>1. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001
%C A003277 Also gcd(n, A051953(n)) = 1. - _Labos Elemer_
%C A003277 n such that x^n == 1 (mod n) has no solution 2 <= x <= n. - _Benoit Cloitre_, May 10 2002
%C A003277 There is only one group (the cyclic group of order n) whose order is n. - _Gerard P. Michon_, Jan 08 2008  [This is a 1947 result of Tibor Szele. - _Charles R Greathouse IV_, Nov 23 2011]
%C A003277 Any divisor of a Carmichael number (A002997) must be odd and cyclic. Conversely, G. P. Michon conjectured (c. 1980) that any odd cyclic number has at least one Carmichael multiple (if the conjecture is true, each of them has infinitely many such multiples). In 2007, Michon & Crump produced explicit Carmichael multiples of all odd cyclic numbers below 10000 (see link, cf. A253595). - _Gerard P. Michon_, Jan 08 2008
%C A003277 Numbers n such that phi(n)^phi(n) == 1 (mod n). - _Michel Lagneau_, Nov 18 2012
%C A003277 Contains A000040, and all members of A006094 except 6. - _Robert Israel_, Jul 08 2015
%C A003277 Number m such that n^n == r (mod m) is solvable for any r. - _David W. Wilson_, Oct 01 2015
%C A003277 Numbers m such that A074792(m) = m + 1. - _Thomas Ordowski_, Jul 16 2017
%C A003277 Squarefree terms of A056867 (see McCarthy link p. 592 and similar comment with "cubefree" in A051532). - _Bernard Schott_, Mar 24 2022
%D A003277 M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
%D A003277 J. S. Rose, A Course on Group Theory, Camb. Univ. Press, 1978, see p. 7.
%D A003277 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003277 T. D. Noe, <a href="/A003277/b003277.txt">Table of n, a(n) for n = 1..10000</a>
%H A003277 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A003277 Max Alekseyev, <a href="http://garden.irmacs.sfu.ca/?q=op/does_every_odd_number_coprime_to_its_euler_totient_divides_some_carmichael_number">Michon's conjecture</a> (Open Problem Garden, Aug. 2007).
%H A003277 Joel E. Cohen, <a href="https://arxiv.org/abs/2508.08335">Conjectures about Primes and Cyclic Numbers</a>, arXiv:2508.08335 [math.NT], 2025. See pp. 1, 2, 30.
%H A003277 Keith Conrad, <a href="https://kconrad.math.uconn.edu/blurbs/grouptheory/allgrouporderncyclic.pdf">When are all groups of order n cyclic?</a>, University of Connecticut, 2019.
%H A003277 Peter J. Dukes and Joanna Niezen, <a href="http://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p098.pdf">Pairwise balanced designs of dimension three</a>, Australasian Journal Of Combinatorics, Volume 61(1) (2015), pages 98-113.
%H A003277 Paul Erdős, <a href="http://www.renyi.hu/~p_erdos/1948-11.pdf">Some asymptotic formulas in number theory</a>, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78.
%H A003277 Jose M. Grau, Manuel Rodríguez, A. Oller-Marcen, and Daniel Sadornil, <a href="http://arxiv.org/abs/1401.4708">Fermat test with gaussian base and Gaussian pseudoprimes</a>, arXiv preprint arXiv:1401.4708 [math.NT], 2014.
%H A003277 Donald J. McCarthy, <a href="https://doi.org/10.1111/j.2164-0947.1971.tb02624.x">A survey of partial converses to Lagrange's theorem on finite groups</a>, Transactions of the New York Academy of Sciences, Vol. 33, No. 6, Series II (1971), pp. 586-594. See page 592.
%H A003277 Gérard P. Michon, <a href="http://www.numericana.com/answer/modular.htm#carmdiv">Carmichael Divisors</a>
%H A003277 Gérard P. Michon and J. K. Crump, <a href="http://www.numericana.com/data/crump.htm">Carmichael Multiples of Odd Cyclic Numbers</a> (up to 10000)
%H A003277 Jonathan Pakianathan and Krishnan Shankar, <a href="http://www.math.ou.edu/%7Eshankar/papers/nil2.pdf">Nilpotent Numbers</a>, Amer. Math. Monthly, 107, August-September 2000, <a href="http://www.jstor.org/stable/2589118">631-634</a>.
%H A003277 R. P. Stanley, <a href="/A003277/a003277.pdf">Letter to N. J. A. Sloane, c. 1991</a>
%H A003277 T. Szele, <a href="http://doi.org/10.5169/seals-18061">Über die endlichen Ordnungszahlen, zu denen nur eine Gruppe gehört</a>, Commentarii Mathematici Helvetici 20 (1947), pp. 265-267.
%H A003277 <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F A003277 n = p_1*p_2*...*p_k (for some k >= 0), where the p_i are distinct primes and no p_j-1 is divisible by any p_i.
%F A003277 A000001(a(n)) = 1.
%F A003277 Erdős proved that a(n) ~ e^gamma n log log log n, where e^gamma is A073004. - _Charles R Greathouse IV_, Nov 23 2011
%F A003277 A000005(a(n)) = 2^k. - _Carlos Eduardo Olivieri_, Jul 07 2015
%F A003277 A008966(a(n)) = 1. - _Bernard Schott_, Mar 24 2022
%p A003277 select(t -> igcd(t, numtheory:-phi(t))=1, [$1..1000]); # _Robert Israel_, Jul 08 2015
%t A003277 Select[Range[175], GCD[#, EulerPhi[#]] == 1 &] (* _Jean-François Alcover_, Apr 04 2011 *)
%t A003277 Select[Range@175, FiniteGroupCount@# == 1 &] (* _Robert G. Wilson v_, Feb 16 2017 *)
%t A003277 Select[Range[200],CoprimeQ[#,EulerPhi[#]]&] (* _Harvey P. Dale_, Apr 10 2022 *)
%o A003277 (PARI) isA003277(n) = gcd(n,eulerphi(n))==1 \\ _Michael B. Porter_, Feb 21 2010
%o A003277 (Haskell)
%o A003277 import Data.List (elemIndices)
%o A003277 a003277 n = a003277_list !! (n-1)
%o A003277 a003277_list = map (+ 1) $ elemIndices 1 a009195_list
%o A003277 -- _Reinhard Zumkeller_, Feb 27 2012
%o A003277 (Magma) [n: n in [1..200] | Gcd(n, EulerPhi(n)) eq 1]; // _Vincenzo Librandi_, Jul 09 2015
%o A003277 (Sage) # Compare A050384.
%o A003277 def isPrimeTo(n, m): return gcd(n, m) == 1
%o A003277 def isCyclic(n): return isPrimeTo(n, euler_phi(n))
%o A003277 [n for n in (1..173) if isCyclic(n)] # _Peter Luschny_, Nov 14 2018
%Y A003277 Subsequence of A051532. Intersection of A056867 and A005117.
%Y A003277 Cf. A000010, A008966, A009195, A050384 (the same sequence but with the primes removed). Also A000001(a(n)) = 1.
%Y A003277 Cf. A002997, A006094, A054395, A055561, A054396, A054397, A056867, A135850, A249550, A249551, A249552, A249553, A249554, A249555, A036537, A051953, A253595.
%K A003277 nonn,nice,easy
%O A003277 1,2
%A A003277 _N. J. A. Sloane_ and _Richard Stanley_
%E A003277 More terms from _Christian G. Bower_