An arithmetic function arising from Carmichael’s conjecture
Journal de Théorie des Nombres de Bordeaux, Volume 23 (2011) no. 3, pp. 697-714.

Let φ denote Euler’s totient function. A century-old conjecture of Carmichael asserts that for every n, the equation φ(n)=φ(m) has a solution mn. This suggests defining F(n) as the number of solutions m to the equation φ(n)=φ(m). (So Carmichael’s conjecture asserts that F(n)2 always.) Results on F are scattered throughout the literature. For example, Sierpiński conjectured, and Ford proved, that the range of F contains every natural number k2. Also, the maximal order of F has been investigated by Erdős and Pomerance. In this paper we study the normal behavior of F. Let

K(x):=(logx)(loglogx)(logloglogx).

We prove that for every fixed ϵ>0,

K(n)1/2-ϵ<F(n)<K(n)3/2+ϵ

for almost all natural numbers n. As an application, we show that φ(n)+1 is squarefree for almost all n. We conclude with some remarks concerning values of n for which F(n) is close to the conjectured maximum size.

Soit φ la fonction indicatrice d’Euler. Une conjecture de Carmichael qui a 100 ans affirme que pour chaque n, l’équation φ(n)=φ(m) a au moins une solution mn. Ceci suggère que l’on définisse F(n) comme le nombre de solutions m de l’équation φ(n)=φ(m). (Donc, la conjecture de Carmichael est équivalente à l’inégalité F(n)2 pour tout n.) Les résultats sur F sont répandus dans la littérature. Par exemple, Sierpiński a conjecturé, et Ford a démontré, que l’image de F contient tous les nombres k2. Aussi, l’ordre maximal de F a été recherché par Erdős et Pomerance. Dans notre article, nous étudions l’ordre normal de F. Soit

K(x):=(logx)(loglogx)(logloglogx).

On démontre que pour chaque ε>0, l’inégalité

K(n)1/2-ε<F(n)<K(n)3/2+ε

est vraie pour presque tous les entiers positifs n. Comme application, on montre que φ(n)+1 est sans facteur carré pour presque tous les n. On conclut avec quelques remarques sur les valeurs de n telles que F(n) est proche de sa valeur maximale conjecturée.

Received:
Published online:
DOI: 10.5802/jtnb.783
Florian Luca 1; Paul Pollack 2

1 Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089, Morelia, Michoacán, México
2 University of Illinois at Urbana-Champaign Department of Mathematics Urbana, Illinois 61801, USA
@article{JTNB_2011__23_3_697_0,
     author = {Florian Luca and Paul Pollack},
     title = {An arithmetic function arising from {Carmichael{\textquoteright}s} conjecture},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {697--714},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {23},
     number = {3},
     year = {2011},
     doi = {10.5802/jtnb.783},
     zbl = {1271.11092},
     mrnumber = {2861081},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.783/}
}
TY  - JOUR
TI  - An arithmetic function arising from Carmichael’s conjecture
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2011
DA  - 2011///
SP  - 697
EP  - 714
VL  - 23
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.783/
UR  - https://zbmath.org/?q=an%3A1271.11092
UR  - https://www.ams.org/mathscinet-getitem?mr=2861081
UR  - https://doi.org/10.5802/jtnb.783
DO  - 10.5802/jtnb.783
LA  - en
ID  - JTNB_2011__23_3_697_0
ER  - 
%0 Journal Article
%T An arithmetic function arising from Carmichael’s conjecture
%J Journal de Théorie des Nombres de Bordeaux
%D 2011
%P 697-714
%V 23
%N 3
%I Société Arithmétique de Bordeaux
%U https://doi.org/10.5802/jtnb.783
%R 10.5802/jtnb.783
%G en
%F JTNB_2011__23_3_697_0
Florian Luca; Paul Pollack. An arithmetic function arising from Carmichael’s conjecture. Journal de Théorie des Nombres de Bordeaux, Volume 23 (2011) no. 3, pp. 697-714. doi : 10.5802/jtnb.783. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.783/

[1] R. C. Baker and G. Harman, Shifted primes without large prime factors. Acta Arith. 83 (1998), 331–361. | EuDML: 207126 | MR: 1610553 | Zbl: 0994.11033

[2] W. D. Banks, J. B. Friedlander, F. Luca, F. Pappalardi, and I. E. Shparlinski, Coincidences in the values of the Euler and Carmichael functions. Acta Arith. 122 (2006), 207–234. | EuDML: 278369 | MR: 2239915 | Zbl: 1195.11128

[3] R. D. Carmichael, On Euler’s φ-function. Bull. Amer. Math. Soc. 13 (1907), 241–243. | JFM: 38.0236.01 | MR: 1558451

[4] —, Note on Euler’s φ-function. Bull. Amer. Math. Soc. 28 (1922), 109–110. | JFM: 48.0158.04 | MR: 1560520

[5] N. G. de Bruijn, Asymptotic methods in analysis. Third ed., Dover Publications Inc., New York, 1981. | MR: 671583 | Zbl: 0556.41021

[6] R. E. Dressler, A density which counts multiplicity. Pacific J. Math. 34 (1970), 371–378. | MR: 271057 | Zbl: 0181.05302

[7] P. Erdős, On the normal number of prime factors of p-1 and some related problems concerning Euler’s φ-function. Quart. J. Math. 6 (1935), 205–213. | JFM: 61.0129.05

[8] —, Some remarks on Euler’s φ-function and some related problems. Bull. Amer. Math. Soc. 51 (1945), 540–544. | MR: 12634 | Zbl: 0061.08005

[9] P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions. Analytic number theory (Allerton Park, IL, 1989), Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 165–204. | MR: 1084181 | Zbl: 0721.11034

[10] P. Erdős and J.-L. Nicolas, Sur la fonction: nombre de facteurs premiers de N. Enseign. Math. (2) 27 (1981), 3–27. | MR: 630957 | Zbl: 0466.10037

[11] P. Erdős and C. Pomerance, On the normal number of prime factors of φ(n). Rocky Mountain J. Math. 15 (1985), 343–352. | MR: 823246 | Zbl: 0617.10037

[12] K. Ford, The distribution of totients. Ramanujan J. 2 (1998), 67–151. | MR: 1642874 | Zbl: 0914.11053

[13] —, The number of solutions of φ(x)=m. Ann. of Math. (2) 150 (1999), 283–311. | EuDML: 121544 | MR: 1715326

[14] A. Granville, Smooth numbers: computational number theory and beyond. Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 267–323. | MR: 2467549 | Zbl: pre05532105

[15] G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n. Quart. J. Math. 58 (1917), 76–92. | JFM: 46.0262.03

[16] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth ed., Oxford University Press, New York, 1979. | MR: 568909 | Zbl: 1159.11001

[17] F. Luca and C. Pomerance, On some problems of Mąkowski-Schinzel and Erdős concerning the arithmetical functions φ and σ. Colloq. Math. 92 (2002), 111–130. | EuDML: 283450 | MR: 1899242 | Zbl: 1027.11007

[18] —, Irreducible radical extensions and Euler-function chains. Combinatorial number theory, de Gruyter, Berlin, 2007, pp. 351–361. | MR: 2337059

[19] P. Pollack, On the greatest common divisor of a number and its sum of divisors. Michigan Math. J. 60 (2011), 199–214. | MR: 2785871 | Zbl: pre05899031

[20] C. Pomerance, Popular values of Euler’s function. Mathematika 27 (1980), 84–89. | MR: 581999 | Zbl: 0437.10001

[21] —, On the distribution of pseudoprimes. Math. Comp. 37 (1981), 587–593. | MR: 628717 | Zbl: 0511.10002

[22] —, Two methods in elementary analytic number theory. Number theory and applications (Banff, AB, 1988), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 135–161. | MR: 1123073 | Zbl: 0683.10003

[23] G. Robin, Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n. Acta Arith. 42 (1983), 367–389. | EuDML: 205883 | MR: 736719 | Zbl: 0475.10034

Cited by Sources: