Sierpiński and Carmichael numbers

Banks, William; Finch, Carrie; Luca, Florian; Pomerance, Carl; Stănică, Pantelimon

doi:10.1090/S0002-9947-2014-06083-2

Sierpiński and Carmichael numbers
HTML articles powered by AMS MathViewer

by William Banks, Carrie Finch, Florian Luca, Carl Pomerance and Pantelimon Stănică PDF

Trans. Amer. Math. Soc. 367 (2015), 355-376 Request permission

Abstract:

We establish several related results on Carmichael, Sierpiński and Riesel numbers. First, we prove that almost all odd natural numbers $k$ have the property that $2^nk+1$ is not a Carmichael number for any $n\in \mathbb {N}$; this implies the existence of a set $\mathscr {K}$ of positive lower density such that for any $k\in \mathscr {K}$ the number $2^nk+1$ is neither prime nor Carmichael for every $n\in \mathbb {N}$. Next, using a recent result of Matomäki and Wright, we show that there are $\gg x^{1/5}$ Carmichael numbers up to $x$ that are also Sierpiński and Riesel. Finally, we show that if $2^nk+1$ is Lehmer, then $n\leqslant 150 \omega (k)^2\log k$, where $\omega (k)$ is the number of distinct primes dividing $k$.

References

W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
W. D. Banks, Carmichael numbers with a square totient, Canad. Math. Bull. 52 (2009), no. 1, 3–8. MR 2494305, DOI 10.4153/CMB-2009-001-7
William D. Banks, Carmichael numbers with a totient of the form $a^2+nb^2$, Monatsh. Math. 167 (2012), no. 2, 157–163. MR 2954522, DOI 10.1007/s00605-011-0306-4
William D. Banks, C. Wesley Nevans, and Carl Pomerance, A remark on Giuga’s conjecture and Lehmer’s totient problem, Albanian J. Math. 3 (2009), no. 2, 81–85. MR 2515950
William D. Banks and Carl Pomerance, On Carmichael numbers in arithmetic progressions, J. Aust. Math. Soc. 88 (2010), no. 3, 313–321. MR 2661452, DOI 10.1017/S1446788710000169
Yann Bugeaud, Pietro Corvaja, and Umberto Zannier, An upper bound for the G.C.D. of $a^n-1$ and $b^n-1$, Math. Z. 243 (2003), no. 1, 79–84. MR 1953049, DOI 10.1007/s00209-002-0449-z
Yann Bugeaud and Florian Luca, A quantitative lower bound for the greatest prime factor of $(ab+1)(bc+1)(ca+1)$, Acta Arith. 114 (2004), no. 3, 275–294. MR 2071083, DOI 10.4064/aa114-3-3
Yann Bugeaud, Maurice Mignotte, and Samir Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers, Ann. of Math. (2) 163 (2006), no. 3, 969–1018. MR 2215137, DOI 10.4007/annals.2006.163.969
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), no. 5, 232–238. MR 1558896, DOI 10.1090/S0002-9904-1910-01892-9
R. D. Carmichael, On Composite Numbers $P$ Which Satisfy the Fermat Congruence $a^{P-1} \equiv 1 \operatorname {mod} P$, Amer. Math. Monthly 19 (1912), no. 2, 22–27. MR 1517641, DOI 10.2307/2972687
Javier Cilleruelo, Florian Luca and Amalia Pizarro-Madariaga, Carmichael numbers in the sequence $\{2^nk+1\}_{n\ge 1}$, Math. Comp., to appear.
P. Corvaja and U. Zannier, On the greatest prime factor of $(ab+1)(ac+1)$, Proc. Amer. Math. Soc. 131 (2003), no. 6, 1705–1709. MR 1955256, DOI 10.1090/S0002-9939-02-06771-0
Pietro Corvaja and Umberto Zannier, A lower bound for the height of a rational function at $S$-unit points, Monatsh. Math. 144 (2005), no. 3, 203–224. MR 2130274, DOI 10.1007/s00605-004-0273-0
Aaron Ekstrom, Carl Pomerance, and Dinesh S. Thakur, Infinitude of elliptic Carmichael numbers, J. Aust. Math. Soc. 92 (2012), no. 1, 45–60. MR 2945676, DOI 10.1017/S1446788712000080
P. Erdős and A. M. Odlyzko, On the density of odd integers of the form $(p-1)2^{-n}$ and related questions, J. Number Theory 11 (1979), no. 2, 257–263. MR 535395, DOI 10.1016/0022-314X(79)90043-X
Jan-Hendrik Evertse, An improvement of the quantitative subspace theorem, Compositio Math. 101 (1996), no. 3, 225–311. MR 1394517
Kevin Ford, The distribution of integers with a divisor in a given interval, Ann. of Math. (2) 168 (2008), no. 2, 367–433. MR 2434882, DOI 10.4007/annals.2008.168.367
Santos Hernández and Florian Luca, On the largest prime factor of $(ab+1)(ac+1)(bc+1)$, Bol. Soc. Mat. Mexicana (3) 9 (2003), no. 2, 235–244. MR 2029272
D. H. Lehmer, On Euler’s totient function, Bull. Amer. Math. Soc. 38 (1932), no. 10, 745–751. MR 1562500, DOI 10.1090/S0002-9904-1932-05521-5
Kaisa Matomäki, Carmichael numbers in arithmetic progressions, J. Aust. Math. Soc. 94 (2013), no. 2, 268–275. MR 3109747, DOI 10.1017/S1446788712000547
E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), no. 6, 125–180 (Russian, with Russian summary); English transl., Izv. Math. 64 (2000), no. 6, 1217–1269. MR 1817252, DOI 10.1070/IM2000v064n06ABEH000314
Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
Corentin Pontreau, A Mordell-Lang plus Bogomolov type result for curves in $\Bbb G^2_m$, Monatsh. Math. 157 (2009), no. 3, 267–281. MR 2520729, DOI 10.1007/s00605-008-0028-4
H. Riesel, Nagra stora primtal, Elementa 39 (1956), 258–260.
W. Sierpiński, Sur un problème concernant les nombres $k\cdot 2^{n}+1$, Elem. Math. 15 (1960), 73–74 (French). MR 117201
G. Tenenbaum, Sur la probabilité qu’un entier possède un diviseur dans un intervalle donné, Compositio Math. 51 (1984), no. 2, 243–263 (French). MR 739737
Paul Turán, On a Theorem of Hardy and Ramanujan, J. London Math. Soc. 9 (1934), no. 4, 274–276. MR 1574877, DOI 10.1112/jlms/s1-9.4.274
Thomas Wright, The impossibility of certain types of Carmichael numbers, Integers 12 (2012), no. 5, 951–964. MR 2988558, DOI 10.1515/integers-2012-0016
Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bull. Lond. Math. Soc. 45 (2013), no. 5, 943–952. MR 3104986, DOI 10.1112/blms/bdt013