A role for generalized Fermat numbers
HTML articles powered by AMS MathViewer
- by John B. Cosgrave and Karl Dilcher PDF
- Math. Comp. 86 (2017), 899-933 Request permission
Abstract:
We define a Gauss factorial $N_n!$ to be the product of all positive integers up to $N$ that are relatively prime to $n\in \mathbb N$. In this paper we study particular aspects of the Gauss factorials $\lfloor \frac {n-1}{M}\rfloor _n!$ for $M=3$ and 6, where the case of $n$ having exactly one prime factor of the form $p\equiv 1\pmod {6}$ is of particular interest. A fundamental role is played by those primes $p\equiv 1\pmod {3}$ with the property that the order of $\frac {p-1}{3}!$ modulo $p$ is a power of 2 or 3 times a power of 2; we call them Jacobi primes. Our main results are characterizations of those $n\equiv \pm 1\pmod {M}$ of the above form that satisfy $\lfloor \frac {n-1}{M}\rfloor _n!\equiv 1\pmod {n}$, $M=3$ or 6, in terms of Jacobi primes and certain prime factors of generalized Fermat numbers. We also describe the substantial and varied computations used for this paper.References
- R. Ballinger and W. Keller, List of primes $k.2^n+1$ for $k<300$. Updated July 2014. http://www.prothsearch.net/riesel.html.
- Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1625181
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603
- CADO-NFS (Crible Algébrique: Distribution, Optimisation - Number Field Sieve). Available at http://cado-nfs.gforge.inria.fr.
- Chris K. Caldwell and Takao Komatsu, Powers of Sierpiński numbers base $B$, Integers 10 (2010), A36, 423–436. MR 2684132, DOI 10.1515/INTEG.2010.036
- J. B. Cosgrave, http://www.johnbcosgrave.com/computations.php
- John B. Cosgrave and Karl Dilcher, Extensions of the Gauss-Wilson theorem, Integers 8 (2008), A39, 15. MR 2472057
- John B. Cosgrave and Karl Dilcher, The multiplicative orders of certain Gauss factorials, Int. J. Number Theory 7 (2011), no. 1, 145–171. MR 2776014, DOI 10.1142/S179304211100396X
- John B. Cosgrave and Karl Dilcher, An introduction to Gauss factorials, Amer. Math. Monthly 118 (2011), no. 9, 812–829. MR 2854003, DOI 10.4169/amer.math.monthly.118.09.812
- J. B. Cosgrave and K. Dilcher, The Gauss-Wilson theorem for quarter-intervals, Acta Math. Hungar. 142 (2014), no. 1, 199–230. MR 3158860, DOI 10.1007/s10474-013-0357-1
- John B. Cosgrave and Karl Dilcher, The multiplicative orders of certain Gauss factorials, II, Funct. Approx. Comment. Math. 54 (2016), no. 1, 73–93. MR 3477736, DOI 10.7169/facm/2016.54.1.7
- Richard E. Crandall, Topics in advanced scientific computation, Springer-Verlag, New York; TELOS. The Electronic Library of Science, Santa Clara, CA, 1996. MR 1392472, DOI 10.1007/978-1-4612-2334-4
- Leonard Eugene Dickson, History of the theory of numbers. Vol. I: Divisibility and primality. , Chelsea Publishing Co., New York, 1966. MR 0245499
- K. Dilcher, http://hdl.handle.net/10222/71449.
- http://factordb.com/.
- GMP-ECM (Elliptic Curve Method for Integer Factorization), available at https://gforge. inria.fr/projects/ecm/.
- P. Gaudry, A. Kruppa, F. Morain, L. Muller, E. Thomé, and P. Zimmermann, cado-nfs, An Implementation of the Number Field Sieve Algorithm. Release 1.0, available from http://cado-nfs.gforge.inria.fr/.
- Henry W. Gould, Combinatorial identities, Henry W. Gould, Morgantown, W. Va., 1972. A standardized set of tables listing 500 binomial coefficient summations. MR 0354401
- T. Aaron Gulliver, Self-reciprocal polynomials and generalized Fermat numbers, IEEE Trans. Inform. Theory 38 (1992), no. 3, 1149–1154. MR 1162838, DOI 10.1109/18.135659
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- Richard H. Hudson and Kenneth S. Williams, Binomial coefficients and Jacobi sums, Trans. Amer. Math. Soc. 281 (1984), no. 2, 431–505. MR 722761, DOI 10.1090/S0002-9947-1984-0722761-X
- Michal Křížek, Florian Luca, and Lawrence Somer, 17 lectures on Fermat numbers, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 9, Springer-Verlag, New York, 2001. From number theory to geometry; With a foreword by Alena Šolcová. MR 1866957, DOI 10.1007/978-0-387-21850-2
- D. H. Lehmer, The distribution of totatives, Canadian J. Math. 7 (1955), 347–357. MR 69199, DOI 10.4153/CJM-1955-038-5
- Maple, a computer algebra system. Available at http://www.maplesoft.com/products/ maple/.
- Tom Müller, A generalization of a theorem by Křížek, Luca, and Somer on elite primes, Analysis (Munich) 28 (2008), no. 4, 375–382. MR 2477353, DOI 10.1524/anly.2008.0922
- Tom Müller, On the Fermat periods of natural numbers, J. Integer Seq. 13 (2010), no. 9, Article 10.9.5, 12. MR 2746253
- Tom Müller and Andreas Reinhart, On generalized elite primes, J. Integer Seq. 11 (2008), no. 3, Article 08.3.1, 15. MR 2429958, DOI 10.1112/s1461157000000504
- OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences. Available at http://oeis.org.
- Paulo Ribenboim, The new book of prime number records, Springer-Verlag, New York, 1996. MR 1377060, DOI 10.1007/978-1-4612-0759-7
- Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1292250, DOI 10.1007/978-1-4612-0251-6
- SageMath, a free open-source mathematics software system licensed under the GPL. Available at http://www.sagemath.org/.
Additional Information
- John B. Cosgrave
- Affiliation: 79 Rowanbyrn, Blackrock, County Dublin, A94 FF86, Ireland
- Email: jbcosgrave@gmail.com
- Karl Dilcher
- Affiliation: Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, B3H 4R2, Canada
- Email: dilcher@mathstat.dal.ca
- Received by editor(s): July 13, 2015
- Received by editor(s) in revised form: August 6, 2015, September 9, 2015, and September 14, 2015
- Published electronically: April 26, 2016
- Additional Notes: This research was supported in part by the NSERC (Canada)
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 899-933
- MSC (2010): Primary 11A07; Secondary 11B65
- DOI: https://doi.org/10.1090/mcom/3111
- MathSciNet review: 3584554