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.

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 123, 127, 131, 133, 137, 139, 141, 143, 145, 149, 151, 157, 159, 161, 163, 167, 173

Offset: 1

Author

N. J. A. Sloane and Richard Stanley

Keywords

• nonn
• nice
• easy

Comments

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

Also gcd(n, A051953(n)) = 1. - Labos Elemer

n such that x^n == 1 (mod n) has no solution 2 <= x <= n. - Benoit Cloitre, May 10 2002

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]

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

Numbers n such that phi(n)^phi(n) == 1 (mod n). - Michel Lagneau, Nov 18 2012

Contains A000040, and all members of A006094 except 6. - Robert Israel, Jul 08 2015

Number m such that n^n == r (mod m) is solvable for any r. - David W. Wilson, Oct 01 2015

Numbers m such that A074792(m) = m + 1. - Thomas Ordowski, Jul 16 2017

Squarefree terms of A056867 (see McCarthy link p. 592 and similar comment with "cubefree" in A051532). - Bernard Schott, Mar 24 2022

References

• 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.
• J. S. Rose, A Course on Group Theory, Camb. Univ. Press, 1978, see p. 7.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
• Max Alekseyev, Michon's conjecture (Open Problem Garden, Aug. 2007).
• Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See pp. 1, 2, 30.
• Keith Conrad, When are all groups of order n cyclic?, University of Connecticut, 2019.
• Peter J. Dukes and Joanna Niezen, Pairwise balanced designs of dimension three, Australasian Journal Of Combinatorics, Volume 61(1) (2015), pages 98-113.
• Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78.
• Jose M. Grau, Manuel Rodríguez, A. Oller-Marcen, and Daniel Sadornil, Fermat test with gaussian base and Gaussian pseudoprimes, arXiv preprint arXiv:1401.4708 [math.NT], 2014.
• Donald J. McCarthy, A survey of partial converses to Lagrange's theorem on finite groups, Transactions of the New York Academy of Sciences, Vol. 33, No. 6, Series II (1971), pp. 586-594. See page 592.
• Gérard P. Michon, Carmichael Divisors
• Gérard P. Michon and J. K. Crump, Carmichael Multiples of Odd Cyclic Numbers (up to 10000)
• Jonathan Pakianathan and Krishnan Shankar, Nilpotent Numbers, Amer. Math. Monthly, 107, August-September 2000, 631-634.
• R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
• T. Szele, Über die endlichen Ordnungszahlen, zu denen nur eine Gruppe gehört, Commentarii Mathematici Helvetici 20 (1947), pp. 265-267.
• Index entries for sequences related to groups

Crossrefs

Subsequence of A051532. Intersection of A056867 and A005117.

Cf. A000010, A008966, A009195, A050384 (the same sequence but with the primes removed). Also A000001(a(n)) = 1.

Cf. A002997, A006094, A054395, A055561, A054396, A054397, A056867, A135850, A249550, A249551, A249552, A249553, A249554, A249555, A036537, A051953, A253595.

Programs

Haskell

import Data.List (elemIndices)
a003277 n = a003277_list !! (n-1)
a003277_list = map (+ 1) $ elemIndices 1 a009195_list
-- Reinhard Zumkeller, Feb 27 2012

Magma

[n: n in [1..200] | Gcd(n, EulerPhi(n)) eq 1]; // Vincenzo Librandi, Jul 09 2015

Maple

select(t -> igcd(t, numtheory:-phi(t))=1, [$1..1000]); # Robert Israel, Jul 08 2015

Mathematica

Select[Range[175], GCD[#, EulerPhi[#]] == 1 &] (* Jean-François Alcover, Apr 04 2011 *)
Select[Range@175, FiniteGroupCount@# == 1 &] (* Robert G. Wilson v, Feb 16 2017 *)
Select[Range[200],CoprimeQ[#,EulerPhi[#]]&] (* Harvey P. Dale, Apr 10 2022 *)

PARI

isA003277(n) = gcd(n,eulerphi(n))==1 \\ Michael B. Porter, Feb 21 2010

Sage

# Compare A050384.
def isPrimeTo(n, m): return gcd(n, m) == 1
def isCyclic(n): return isPrimeTo(n, euler_phi(n))
[n for n in (1..173) if isCyclic(n)] # Peter Luschny, Nov 14 2018

Formula

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.

A000001(a(n)) = 1.

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

A000005(a(n)) = 2^k. - Carlos Eduardo Olivieri, Jul 07 2015

A008966(a(n)) = 1. - Bernard Schott, Mar 24 2022

Extensions

More terms from Christian G. Bower