A011773 -id:A011773 - cp's OEIS frontend

A199105 Numbers k such that lambda(k) < A011773(k) < phi(k), where lambda is the Carmichael reduced totient function and phi the Euler totient function.

24, 48, 56, 72, 80, 88, 96, 112, 144, 152, 160, 168, 176, 184, 192, 208, 216, 224, 240, 248, 264, 288, 304, 320, 336, 344, 352, 368, 376, 384, 392, 400, 416, 432, 448, 456, 464, 472, 480, 496, 504, 528, 536, 552, 560, 568, 576, 592, 608, 616, 624

Offset: 1

José María Grau Ribas, Jan 31 2012

nonn

A002322(k) divides A011773(k) and A011773(k) divides A000010(k).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A002322, A011773.

A011773[p_,s_] := (p-1)*p^(s-1); A011773[n_] := {aux=1;Do[aux=LCM[aux,A011773[FactorInteger[n][[i,1]], FactorInteger[n][[i,2]]]], {i,Length[FactorInteger[n]]}]; aux}[[1]]; Select[Range[1000], CarmichaelLambda[#] < A011773[#] < EulerPhi[#]&]

A002322 Reduced totient function psi(n): least k such that x^k == 1 (mod n) for all x prime to n; also known as the Carmichael lambda function (exponent of unit group mod n); also called the universal exponent of n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18, 4, 6, 10, 22, 2, 20, 12, 18, 6, 28, 4, 30, 8, 10, 16, 12, 6, 36, 18, 12, 4, 40, 6, 42, 10, 12, 22, 46, 4, 42, 20, 16, 12, 52, 18, 20, 6, 18, 28, 58, 4, 60, 30, 6, 16, 12, 10, 66, 16, 22, 12, 70, 6, 72, 36, 20, 18, 30, 12, 78, 4, 54

Offset: 1

N. J. A. Sloane

a(n) is the largest order of any element in the multiplicative group modulo n. - Joerg Arndt, Mar 19 2016

Largest period of repeating digits of 1/n written in different bases (i.e., largest value in each row of square array A066799 and least common multiple of each row). - Henry Bottomley, Dec 20 2001

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 53.
Kenneth H. Rosen, Elementary Number Theory and Its Applications, Addison-Wesley, 1984, page 269.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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
L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364-383. see p. 377.
P. J. Cameron and D. A. Preece, Notes on primitive lambda-roots
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1909-10), 232-238.
A. Cauchy, Mémoire sur la résolution des équations indéterminées du premier degré en nombres entiers, Oeuvres Complètes. Gauthier-Villars, Paris, 1882-1938, Series (2), Vol. 12, pp. 9-47.
A. de Vries, The prime factors of an integer(along with Euler's phi and Carmichael's lambda functions), Applet
Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael's lambda function, Acta Arithmetica 58 (1991), pp. 363-385.
J.-H. Evertse and E. van Heyst, Which new RSA signatures can be computed from some given RSA signatures?, Proceedings of Eurocrypt '90, Lect. Notes Comput. Sci., 473, Springer-Verlag, pp. 84-97, see page 86.
J. M. Grau and A. M. Oller-Marcén, On the congruence sum_{j=1}^{n-1} j^{k(n-1)} == -1 (mod n); k-strong Giuga and k-Carmichael numbers, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 80.
Benjamin Schreyer, Rigged Horse Numbers and their Modular Periodicity, arXiv:2409.03799 [math.CO], 2024. See p. 12.
Eric Weisstein's World of Mathematics, Carmichael Function
Wikipedia, Carmichael function
Wolfram Research, First 50 values of Carmichael lambda(n)
Index entries for "core" sequences

Cf. A011773, A002174, A002616, A034380, A061258, A062373, A141258, A162578 (partial sums), A218342.

a002322 n = foldl lcm 1 $ map (a207193 . a095874) $
                          zipWith (^) (a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Feb 16 2012

[1] cat [ CarmichaelLambda(n) : n in [2..100]];

with(numtheory); A002322 := lambda; [seq(lambda(n), n=1..100)];

Table[CarmichaelLambda[k], {k, 50}] (* Artur Jasinski, Apr 05 2008 *)

A002322(n)= lcm( apply( f -> (f[1]-1)*f[1]^(f[2]-1-(f[1]==2 && f[2]>2)), Vec(factor(n)~))) \\ M. F. Hasler, Jul 05 2009

a(n)=lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Aug 04 2012

from sympy import reduced_totient
def A002322(n): return reduced_totient(n) # Chai Wah Wu, Feb 24 2021

If M = 2^e*P1^e1*P2^e2*...*Pk^ek, lambda(2^e) = 2^(e-1) if e=1 or 2, = 2^(e-2) if e > 2; lambda(M) = lcm(lambda(2^e), (P1-1)*P1^(e1-1), (P2-1)*P2^(e2-1), ..., (Pk-1)*Pk^(ek-1)).

a(n) = lcm_{k=1..A001221(n)} A207193(A095874(A027748(n,k)^A124010(n,k))). - Reinhard Zumkeller, Feb 16 2012

A174824 a(n) = period of the sequence {m^m, m >= 1} modulo n.

Original entry on oeis.org

1, 2, 6, 4, 20, 6, 42, 8, 18, 20, 110, 12, 156, 42, 60, 16, 272, 18, 342, 20, 42, 110, 506, 24, 100, 156, 54, 84, 812, 60, 930, 32, 330, 272, 420, 36, 1332, 342, 156, 40, 1640, 42, 1806, 220, 180, 506, 2162, 48, 294, 100, 816, 156, 2756, 54, 220, 168, 342

Offset: 1

Franklin T. Adams-Watters, Mar 30 2010

nonn

This is a divisibility sequence: if n divides m, a(n) divides a(m).

We have the equality n = a(n) for numbers n in A124240, which is related to Carmichael's function (A002322). The largest values of a(n) occur when n is prime, in which case a(n) = n*(n-1). - T. D. Noe, Feb 21 2014

			For n=3, 1^1 == 1 (mod 3), 2^2 == 1 (mod 3), 3^3 == 0 (mod 3), etc. The sequence of residues 1, 1, 0, 1, 2, 0, 1, 1, 0, ... has period 6, so a(3) = 6. - _Michael B. Porter_, Mar 13 2018

T. D. Noe, Table of n, a(n) for n = 1..1000
José María Grau and Antonio M. Oller-Marcén, On the last digit and the last non-zero digit of n^n in base b, arXiv:1203.4066 [math.NT], 2012. (See page 3)
Index to divisibility sequences

Cf. A000312, A009262, A127699.

Cf. A002322, A124240, A268336.

Table[LCM[n, CarmichaelLambda[n]], {n, 100}] (* T. D. Noe, Feb 20 2014 *)

a(n)=local(ps);ps=factor(n)[,1]~;for(k=1,#ps,n=lcm(n,ps[k]-1));n

a(n) = lcm(n, lcm(znstar(n)[2])); \\ Michel Marcus, Mar 18 2016; corrected by Michel Marcus, Nov 13 2019

apply( {A174824(n)=lcm(lcm([p-1|p<-factor(n)[,1]]),n)}, [1..99]) \\ [...] = znstar(n)[2], but 3x faster. - M. F. Hasler, Nov 13 2019

a(n) = lcm(n, A173614(n)) = lcm(n, A002322(n)) = lcm(n, A011773(n)).
If n and m are relatively prime, a(n*m) = lcm(a(n), a(m)); a(p^k) = (p-1)*p^k for p prime and k > 0.
a(n) = n*A268336(n). - M. F. Hasler, Nov 13 2019

A174590 a(n) = (k-1)/lambda(k), the index of the n-th Carmichael number k.

Original entry on oeis.org

7, 23, 48, 22, 47, 5, 45, 21, 44, 163, 342, 162, 43, 31, 1777, 314, 337, 161, 1753, 70, 2868, 1745, 421, 2487, 1363, 159, 39, 645, 950, 67, 198, 1358, 949, 158, 2303, 134, 305, 1692, 1733, 5731, 2794, 7107, 1732, 345, 1689, 2654, 1671, 1829, 947, 1353, 1557

Offset: 1

Michel Lagneau, Mar 23 2010, Mar 31 2010

nonn

The index of a Carmichael number k is i(k) = (k-1)/lambda(k).
Or, i(k) = (k-1)/lcm(p_1-1,p_2-1,...,p_j-1), where k = p_1*p_2*...*p_j. - Thomas Ordowski, Oct 15 2015
For composite k, lambda(k) divides k-1 iff k is a Carmichael number. - Thomas Ordowski, Oct 23 2015

			a(1)= 7 because A002997(1) = 561, and (561 - 1)/lambda(561) = 560/80 = 7.

Robert Israel, Table of n, a(n) for n = 1..10000
J. M. Chick, Carmichael number variable relations: three-prime Carmichael numbers up to 10^24, arXiv:0711.2915 [math.NT] 2007-2008, Table 1, p. 34.
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883-908.
R. G. E. Pinch, Carmichael numbers up to 10^18, April 2006.
Richard Pinch, Carmichael Numbers up to 10^20, Abstract, ANTS 7.
Richard Pinch, Carmichael Numbers up to 10^20, Poster, ANTS 7.

Cf. A002322 (the Carmichael lambda function), A002997, A011773, A306414.

with(numtheory) : for n from 2 to 2000000 do: if type(n,prime)=false and issqrfree(n)=true then  x:=factorset(n):n1:=nops(x):ii:=0:for j from 1 to n1 do:if irem(n-1, x[j]-1)=0  then ii:=ii+1:else fi:od:if ii=n1 then z:=(n-1)/lambda(n):printf(`%d, `,z):else fi:fi:od:

carNums = Select[Range[561, 3 10^6, 2], CompositeQ[#] && Mod[#, CarmichaelLambda[#]] == 1&];
a[n_] := (carNums[[n]] - 1)/CarmichaelLambda[carNums[[n]]];
Array[a, 60] (* Jean-François Alcover, Sep 05 2018 *)

t(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1;
for(n=1, 1e7, if(n%2 && !isprime(n) && t(n) && n>1, print1((n-1)/(lcm(znstar(n)[2])), ", "))) \\ Altug Alkan, Oct 15 2015

a(n) = (A002997(n) - 1) / lambda(A002997(n)).

a(n) = (A002997(n) - 1) / A306414(n). - Jianing Song, Dec 12 2021

Edited by Michel Lagneau, Jul 31 2012

Further edits from N. J. A. Sloane, Oct 31 2015

A102818 Irregular array a(m,k) = A001035(k) mod m read by rows, 1<=k<=16, 3<=m.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 4, 4, 1, 3, 4, 4, 1, 3, 4, 4, 1, 3, 4, 4, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 5, 2, 3, 5, 1, 3, 5, 2, 3, 5, 1, 3, 5, 2, 1, 3, 3, 3, 7, 7, 3, 3, 7, 7, 3, 3, 7, 7, 3, 3, 1, 3, 1, 3, 1, 0, 4, 3, 1

Offset: 3

Gerald McGarvey, Feb 26 2005

Conjectures (based on mod values up to n=99): the sequence A001035(m) is (pre)periodic modulo n for all n, the lengths of the ending periods mod n (except n=4) being given by A011773 (which is related to Carmichael's lambda function).

			The array starts in row m=3 as:
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0;
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3;
1 3 4 4 1 3 4 4 1 3 4 4 1 3 4 4;
1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3;
1 3 5 2 3 5 1 3 5 2 3 5 1 3 5 2;
1 3 3 3 7 7 3 3 7 7 3 3 7 7 3 3;
1 3 1 3 1 0 4 3 1 3 1 0 4 3 1 3;
1 3 9 9 1 3 9 9 1 3 9 9 1 3 9 9;
1 3 8 10 7 3 10 10 1 6 1 3 8 10 7 3;
1 3 7 3 7 3 7 3 7 3 7 3 7 3 7 3;

Eric Weisstein's World of Mathematics, Carmichael Function

Cf. A001035, A011773, A002322.

seq = List[1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579] Table[Mod[seq, i], {i, 3, 9}]

A096226 a(n) is the least exponent k > 1 such that m^k is congruent to m modulo n for all natural numbers m, or a(n) = 1 if no such k exists.

Original entry on oeis.org

2, 2, 3, 1, 5, 3, 7, 1, 1, 5, 11, 1, 13, 7, 5, 1, 17, 1, 19, 1, 7, 11, 23, 1, 1, 13, 1, 1, 29, 5, 31, 1, 11, 17, 13, 1, 37, 19, 13, 1, 41, 7, 43, 1, 1, 23, 47, 1, 1, 1, 17, 1, 53, 1, 21, 1, 19, 29, 59, 1, 61, 31, 1, 1, 13, 11, 67, 1, 23, 13, 71, 1, 73, 37, 1, 1, 31, 13, 79, 1, 1, 41, 83, 1

Offset: 1

Franz Vrabec, Aug 09 2004

If n is squarefree, a(n) = 1+A002322(n) = 1+A011773(n). Otherwise a(n) = 1. a(n) = n iff n is prime.

			a(35) = 13 because 35 divides 1^13-1, 2^13-2, 3^13-3, etc.; but 35 does not divide 2^2-2, 2^3-3, 2^4-2, ..., 2^11-2 or 2^12-2.

Cf. A002322, A011773.

For squarefree n = p1*p2*...*pj, a(n) = 1+lcm(p1-1, p2-1, ..., pj-1).

Edited and extended by David Wasserman, Oct 30 2007

cp's OEIS Frontend

A199105 Numbers k such that lambda(k) < A011773(k) < phi(k), where lambda is the Carmichael reduced totient function and phi the Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A002322 Reduced totient function psi(n): least k such that x^k == 1 (mod n) for all x prime to n; also known as the Carmichael lambda function (exponent of unit group mod n); also called the universal exponent of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A174824 a(n) = period of the sequence {m^m, m >= 1} modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A174590 a(n) = (k-1)/lambda(k), the index of the n-th Carmichael number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A102818 Irregular array a(m,k) = A001035(k) mod m read by rows, 1<=k<=16, 3<=m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A096226 a(n) is the least exponent k > 1 such that m^k is congruent to m modulo n for all natural numbers m, or a(n) = 1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions