A074792 -id:A074792 - 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.

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

N. J. A. Sloane and Richard Stanley

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

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).

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

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.

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

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

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

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 *)

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

# 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

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

More terms from Christian G. Bower

A076943 Smallest k > 0 such that n*k + 1 is an n-th power.

Original entry on oeis.org

1, 4, 21, 20, 1555, 2604, 299593, 820, 29127, 348678440, 67546215517, 20345052, 61054982558011, 281241170407092, 76861433640456465, 2690420, 128583032925805678351, 211927625868, 275941052631578947368421, 174339220

Offset: 1

Amarnath Murthy, Oct 19 2002

			For n = 7, 1 + 7*a(7) = 1 + 7*299593 = 2097152 = 2^21 = 8^7.
For n = 10, 1 + 10*a(10) = 1 + 10*348678440 = 3486784401 = 3^20 = 9^10. - _Marius A. Burtea_, Jun 01 2019

Marius A. Burtea, Table of n, a(n) for n = 1..150

Cf. A076942, A076944, A074792.

sol:=[];
for u in [1..20] do
   for k in [2..100] do
      if IsIntegral((k^u-1)/u) then sol[u]:=(k^u-1)/u; break; end if;
   end for;
end for;
sol; // Marius A. Burtea, Jun 01 2019

Do[k = 2; While[ !IntegerQ[(k^n - 1)/n], k++ ]; Print[(k^n - 1)/n], {n, 1, 20}] (* Robert G. Wilson v, Oct 21 2002 *)

a(n) <= ((n+1)^n - 1) / n.
a(p^k) = ((p+1)^(p^k) - 1) / p^k. - Charlie Neder, May 23 2019
a(2*p) = ((2*p-1)^(2*p) - 1) / (2*p). - Charlie Neder, May 23 2019

Edited, corrected and extended by Robert G. Wilson v, Oct 21 2002

A083503 Basis of the n-th power arising in A083502.

Original entry on oeis.org

3, 3, 4, 3, 6, 5, 8, 3, 4, 9, 12, 5, 14, 13, 16, 3, 18, 5, 20, 3, 4, 21, 24, 5, 6, 25, 4, 13, 30, 11, 32, 3, 34, 33, 36, 5, 38, 37, 16, 3, 42, 5, 44, 21, 16, 45, 48, 5, 8, 9, 52, 5, 54, 5, 16, 13, 7, 57, 60, 7, 62, 61, 4, 3, 66, 23, 68, 13, 70, 29, 72, 5, 74, 73, 16, 37, 78, 17, 80, 3, 4

Offset: 1

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), May 03 2003

nonn

For n > 1, a(n) = A074792(n) is the least solution > 1 of x^n == 1 (mod n). - Robert Israel, Aug 01 2025

			2*(2+2)+1=3^2; 3*(3+18)+1=4^3; 4*(4+16)+1=3^4; 5*(5+1550)+1=6^5; 6*(6+2598)+1=5^6; 7*(7+299586)+1=8^7; 8*(8+812)+1=3^8; 9*(9+29118)+1=4^9; 10*(10+348678430)+1=9^10. - _R. J. Mathar_, Aug 01 2025

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A083502, A074792.

A083503 := proc(n)
    local a,b ;
    if n = 1 then
        3 ;
    else
        for b from 2 do
            a := (b^n-1)/n-n ;
            if type( a,'integer') then
                return  b;
            end if;
        end do:
    end if;
end proc:
seq(A083503(n),n=1..80) ; # R. J. Mathar, Aug 01 2025
# alternative:
f:= proc(n) local X,S;
  S:= min(map(t -> subs(t,X), {msolve(X^n = 1, n)} minus {{X=1}}));
  if S = infinity then n+1 else S fi
end proc:
f(1):= 3:
map(f, [$1..100]); # Robert Israel, Aug 01 2025

Do[i = 2; While[k = (i^n - 1)/n - n; !IntegerQ[k], i++ ]; Print[i], {n, 2, 81}]

n*(n + A083502(n)) + 1 = a(n)^n. - R. J. Mathar, Aug 01 2025

Edited and extended by Robert G. Wilson v, May 11 2003

A110738 a(n) = common ratio for row n in A112668.

Original entry on oeis.org

1, 3, 4, 3, 6, 5, 8, 3, 4, 9, 12, 5, 14, 13, 16, 3, 18, 5, 20, 3, 4, 21, 24, 5, 6, 25, 4, 13, 30, 11, 32, 3, 34, 33, 36, 5, 38, 37, 16, 3, 42, 5, 44, 21, 16, 45, 48, 5, 8, 9, 52, 5, 54, 5, 16, 13, 7, 57, 60, 7, 62, 61, 4, 3, 66, 23, 68, 13, 70, 29, 72, 5, 74, 73, 16, 37, 78, 17, 80, 3

Offset: 1

Amarnath Murthy, Aug 10 2005

Cf. A110737, A110739.

Cf. A074792, A083503.

A110738 := proc(n) local a ; if n = 1 then RETURN(1) ; else a := 2 ; while (1-a^n)/(1-a) mod n <> 0 do a := a+1 ; od ; RETURN(a) ; fi ; end: for n from 1 to 80 do printf("%d, ",A110738(n)) : od : # R. J. Mathar, Mar 13 2007

More terms from R. J. Mathar, Mar 13 2007

A284761 a(n) = gcd(A279513(n), A279513(n+1)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 4, 2, 1, 1, 1, 1, 1, 3

Offset: 1

Rémy Sigrist, Apr 02 2017

nonn

Two consecutive numbers, say n and n+1, cannot share a prime factor (gcd(n, n+1)=1). However, their prime tower factorizations can share some prime numbers; this is the case iff a(n)>1 (see A182318 for the definition of the prime tower factorization of a number).
If p is prime, then a(p-1) = a(p) = 1.
If p is an odd prime, then a(p^2) = 2.
This sequence contains a multiple of p for any prime p:
- let m = A074792(p)^p-1,
- m is a multiple of p, hence p divides A279513(m),
- m+1 = A074792(p)^p, hence p divides A279513(m+1),
- hence p divides gcd(A279513(m), A279513(m+1)) = a(m).
This sequence contains infinitely many distinct values; see A284821 for these distinct values in order of appearance, and A284822 for the corresponding indexes.

			a(8) = gcd(A279513(8), A279513(9)) = gcd(A279513(2^3), A279513(3^2)) = gcd(2*3, 3*2) = 6.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Illustration of the first terms

Cf. A074792, A182318, A284821, A284822.

A076944 Least number such that n*k+1 is an n-th power.

Original entry on oeis.org

2, 9, 64, 81, 7776, 15625, 2097152, 6561, 262144, 3486784401, 743008370688, 244140625, 793714773254144, 3937376385699289, 1152921504606846976, 43046721, 2185911559738696531968, 3814697265625

Offset: 1

Amarnath Murthy, Oct 19 2002

nonn

a(n) <= {(n+1)^n - 1}/n.

Cf. A076942, A076943, A074792.

Do[k = 2; While[ !IntegerQ[(k^n - 1)/n], k++ ]; Print[k^n], {n, 1, 19}]

a(n) = n*A076943(n) + 1.

Edited, corrected and extended by Robert G. Wilson v, Oct 21 2002

A319813 a(n) is the smallest a such that n is divisible by a^n + 1, or 0 if no such a exists.

Original entry on oeis.org

1, 1, 2, 0, 4, 0, 6, 0, 2, 3, 10, 0, 12, 0, 14, 0, 16, 0, 18, 0, 5, 0, 22, 0, 4, 5, 2, 0, 28, 0, 30, 0, 32, 13, 34, 0, 36, 0, 17, 0, 40, 0, 42, 0, 14, 0, 46, 0, 6, 3, 50, 0, 52, 0, 19, 0, 8, 17, 58, 0, 60, 0, 5, 0, 64, 0, 66, 0, 68, 0, 70, 0, 72, 31, 14, 0, 76

Offset: 1

Jianing Song, Sep 28 2018

nonn

a(n) = 0 iff n is even and -1 is not a square modulo n, that is, n is even and not in A008784. For other n > 2, 2 <= a(n) <= n - 1.
a(p) = p - 1 for primes p. For composite n, a(n) = n - 1 iff gcd(n, phi(n)) = 1, that is, n is in A050384.
a(A006521(n)) = 2.

Jianing Song, Table of n, a(n) for n = 1..7000

Cf. A074792 (a^n - 1 instead of a^n + 1).

Cf. also A006521, A008784, A050384.

a(n) = if(!(n%2)&&!issquare(Mod(-1,n)), 0, my(i=1); while(Mod(i,n)^n!=n-1, i++); i)

For n = 9, 9 is divisible by a^9 + 1 implies a == 2 (mod 3), so a(9) = 2.
For n = 10, 10 is divisible by a^10 + 1 implies a == 3, 7 (mod 10), so a(10) = 3.
For n = 34, 34 is divisible by a^34 + 1 implies a == 13, 21 (mod 34), so a(34) = 13.

cp's OEIS Frontend

A076945 Duplicate of A074792.

Views

Author

Keywords

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A076943 Smallest k > 0 such that n*k + 1 is an n-th power.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A083503 Basis of the n-th power arising in A083502.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A110738 a(n) = common ratio for row n in A112668.

Views

Author

Keywords

Crossrefs

Programs

Maple

Extensions

A284761 a(n) = gcd(A279513(n), A279513(n+1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A076944 Least number such that n*k+1 is an n-th power.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A319813 a(n) is the smallest a such that n is divisible by a^n + 1, or 0 if no such a exists.

Views

Author

Keywords

Comments

Links

Crossrefs