×

zbMATH — the first resource for mathematics

Higher-order Carmichael numbers. (English) Zbl 0966.11006
By generalizing a characterization of a Carmichael number \(n\) by means of cyclic \(\mathbb{Z}/n\mathbb{Z}\)-modules the author defined a Carmichael number of order \(m\) to be a composite integer \(n>0\) such that \(n\)th-power raising defines an endomorphism of every \(\mathbb{Z}/n \mathbb{Z}\)-algebra that can be generated as a \(\mathbb{Z}/n \mathbb{Z}\)-module by \(m\) elements. These numbers can be described by the conditions a) \(n\) is squarefree, b) for every prime divisor \(p\) of \(n\) and for every integer \(r\) with \(1\leq r\leq m\), there is an integer \(i\geq 0\) such that \(n\equiv p^i\bmod (p^r-1)\). The main part of the paper is devoted to the introduction of a method which at least in the case \(m=2\) allows to construct some Carmichael numbers of order \(m\). Finally a characterization of a special type of such numbers by means of finite étale algebras is given.

MSC:
11A51 Factorization; primality
11N25 Distribution of integers with specified multiplicative constraints
11Y11 Primality
13B40 Étale and flat extensions; Henselization; Artin approximation
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1 – 15. · Zbl 0614.10005
[2] William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255 – 300. · Zbl 0492.10005
[3] W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703 – 722. · Zbl 0816.11005 · doi:10.2307/2118576 · doi.org
[4] Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391 – 1417. · Zbl 0458.10003
[5] Adina Di Porto and Piero Filipponi, Generating \?-strong Fibonacci pseudoprimes, Fibonacci Quart. 30 (1992), no. 4, 339 – 343. · Zbl 0767.11006
[6] Adina Di Porto, Piero Filipponi, and Emilio Montolivo, On the generalized Fibonacci pseudoprimes, Fibonacci Quart. 28 (1990), no. 4, 347 – 354. · Zbl 0722.11011
[7] P. ERDSOS: On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. · Zbl 0074.27105
[8] J. GRANTHAM: Frobenius pseudoprimes, Math. Comp. (to appear). · Zbl 1011.11079
[9] S. Gurak, Cubic and biquadratic pseudoprimes of Lucas type, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 330 – 347.
[10] Chih-Nung Hsu, On Carmichael polynomials, J. Number Theory 71 (1998), no. 2, 257 – 274. · Zbl 0922.11105 · doi:10.1006/jnth.1998.2227 · doi.org
[11] I. Joó, On generalized Lucas pseudoprimes, Acta Math. Hungar. 55 (1990), no. 3-4, 279 – 284. · Zbl 0615.10017 · doi:10.1007/BF01950936 · doi.org
[12] A. KORSELT: Problème chinois, L’Intermédiaire des Mathématiciens 6 (1899), 142-143.
[13] G. Kowol, On strong Dickson pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 3 (1992), no. 2, 129 – 138. · Zbl 0761.11044 · doi:10.1007/BF01387195 · doi.org
[14] James S. Milne, Étale cohomology, Princeton Mathematical Series, vol. 33, Princeton University Press, Princeton, N.J., 1980. · Zbl 0433.14012
[15] Rudolf Lidl and Winfried B. Müller, A note on strong Fibonacci pseudoprimes, Advances in cryptology — AUSCRYPT ’90 (Sydney, 1990) Lecture Notes in Comput. Sci., vol. 453, Springer, Berlin, 1990, pp. 311 – 317. · Zbl 0726.11003 · doi:10.1007/BFb0030371 · doi.org
[16] Rudolf Lidl and Winfried B. Müller, Generalizations of the Fibonacci pseudoprimes test, Discrete Math. 92 (1991), no. 1-3, 211 – 220. · Zbl 0749.11013 · doi:10.1016/0012-365X(91)90282-7 · doi.org
[17] Rudolf Lidl and Winfried B. Müller, Primality testing with Lucas functions, Advances in cryptology — AUSCRYPT ’92 (Gold Coast, 1992) Lecture Notes in Comput. Sci., vol. 718, Springer, Berlin, 1993, pp. 539 – 542. · Zbl 0871.11093 · doi:10.1007/3-540-57220-1_92 · doi.org
[18] Rudolf Lidl, Winfried B. Müller, and Alan Oswald, Some remarks on strong Fibonacci pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 1 (1990), no. 1, 59 – 65. · Zbl 0726.11002 · doi:10.1007/BF01810848 · doi.org
[19] František Marko, A note on pseudoprimes with respect to abelian linear recurring sequence, Math. Slovaca 46 (1996), no. 2-3, 173 – 176. · Zbl 0888.11006
[20] G. MARTIN: Lower bounds for the number of smooth values of a polynomial, electronic preprint available online at http://xxx.lanl.gov/abs/math.NT/9807102, 1998.
[21] Siguna M. S. Müller, Carmichael numbers and Lucas tests, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997) Contemp. Math., vol. 225, Amer. Math. Soc., Providence, RI, 1999, pp. 193 – 202. · Zbl 0918.11004 · doi:10.1090/conm/225/03221 · doi.org
[22] Winfried B. Müller and Alan Oswald, Generalized Fibonacci pseudoprimes and probable primes, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992) Kluwer Acad. Publ., Dordrecht, 1993, pp. 459 – 464. · Zbl 0806.11004
[23] R. G. E. Pinch, The Carmichael numbers up to 10\textonesuperior \(^{5}\), Math. Comp. 61 (1993), no. 203, 381 – 391. · Zbl 0780.11069
[24] R. G. E. PINCH: Compressed text file carmichael-16.gz, available by anonymous ftp at ftp://ftp.dpmms.cam.ac.uk/pub/rgep/Carmichael, 1992.
[25] C. POMERANCE: Are there counterexamples to the Baillie-PSW primality test?, Dopo le Parole , privately published, Amsterdam, 1984.
[26] G. Szekeres, Higher order pseudoprimes in primality testing, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 451 – 458. · Zbl 0855.11065
[27] H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133 – 143. · Zbl 0368.10011 · doi:10.4153/CMB-1977-025-9 · doi.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.