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

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.

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.

Reçu le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.783
@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
AU  - Florian Luca
AU  - Paul Pollack
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  - 
Florian Luca; Paul Pollack. An arithmetic function arising from Carmichael’s conjecture. Journal de Théorie des Nombres de Bordeaux, Tome 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

Cité par Sources :