Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A covering system with least modulus 25

Author: Donald Jason Gibson
Journal: Math. Comp. 78 (2009), 1127-1146
MSC (2000): Primary 11B25; Secondary 11A07, 11B75
Published electronically: September 10, 2008
Supplement: Table supplement to this article.
MathSciNet review: 2476575
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A collection of congruences with distinct moduli, each greater than $ 1$, such that each integer satisfies at least one of the congruences, is said to be a covering system. A famous conjecture of Erdös from 1950 states that the least modulus of a covering system can be arbitrarily large. This conjecture remains open and, in its full strength, appears at present to be unattackable. Most of the effort in this direction has been aimed at explicitly constructing covering systems with large least modulus. Improving upon previous results of Churchhouse, Krukenberg, Choi, and Morikawa, we construct a covering system with least modulus $ 25$. The construction involves a large-scale computer search, in conjunction with two general results that considerably reduce the complexity of the search.

References [Enhancements On Off] (What's this?)

  • 1. Marc A. Berger, Alexander Felzenbaum, and Aviezri S. Fraenkel, Necessary condition for the existence of an incongruent covering system with odd moduli. II, Acta Arith. 48 (1987), no. 1, 73-79. MR 893463 (88j:11002)
  • 2. S. L. G. Choi, Covering the set of integers by congruence classes of distinct moduli, Math. Comp. 25 (1971), 885-895. MR 0297692 (45:6744)
  • 3. R. F. Churchhouse, Covering sets and systems of congruences, Computers in Mathematical Research, North-Holland, Amsterdam, 1968, pp. 20-36. MR 0240045 (39:1399)
  • 4. P. Erdös, On integers of the form $ 2\sp k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113-123. MR 0044558 (13:437i)
  • 5. -, On some of my problems in number theory I would most like to see solved, Number theory (Ootacamund, 1984), Lecture Notes in Math., vol. 1122, Springer, Berlin, 1985, pp. 74-84. MR 797781
  • 6. P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique [Monographs of L'Enseignement Mathématique], vol. 28, Université de Genève L'Enseignement Mathématique, Geneva, 1980. MR 592420 (82j:10001)
  • 7. Michael Filaseta, Coverings of the integers associated with an irreducibility theorem of A. Schinzel, Number theory for the millennium, II (Urbana, IL, 2000), A K Peters, Natick, MA, 2002, pp. 1-24. MR 1956242 (2003k:11015)
  • 8. Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance, and Gang Yu, Sieving by large integers and covering systems of congruences, J. Amer. Math. Soc. 20 (2007), no. 2, 495-517 (electronic). MR 2276778
  • 9. Donald Jason Gibson, Covering systems, Ph.D. thesis, University of Illinois, Urbana-Champaign, 2006.
  • 10. Song Guo and Zhi-Wei Sun, On odd covering systems with distinct moduli, Adv. in Appl. Math. 35 (2005), no. 2, 182-187. MR 2152886 (2006e:11018)
  • 11. Richard K. Guy, Unsolved problems in number theory, Third Edition, Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335 (2005h:11003)
  • 12. Ivan Korec and Štefan Znám, On disjoint covering of groups by their cosets, Math. Slovaca 27 (1977), no. 1, 3-7. MR 0485421 (58:5260)
  • 13. C. E. Krukenberg, Covering sets of the integers, Ph.D. thesis, University of Illinois, Urbana-Champaign, 1971.
  • 14. Ryozo Morikawa, On a method to construct covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 22 (1981), no. 1, 1-11. MR 639636 (84i:10057)
  • 15. -, Some examples of covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 21 (1981), no. 2, 1-4. MR 639635 (84j:10064)
  • 16. Pace Nielsen, A covering system whose smallest modulus is large, preprint.
  • 17. Š. Porubský and J. Schönheim, Covering systems of Paul Erdős. Past, present and future, Paul Erdős and his mathematics, I (Budapest, 1999), Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 581-627. MR 1954716 (2004d:11006)
  • 18. N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), 668-678. MR 1512916
  • 19. A. Schinzel, Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967/1968), 91-101. MR 0219515 (36:2596)
  • 20. J. Schönheim, Covering congruences related to modular arithmetic and error correcting codes, Ars Combin. 16 (1983), no. B, 21-25. MR 737106 (85d:11007)
  • 21. W. Sierpiński, Sur un problème concernant les nombres $ k\cdot 2\sp{n}+1$, Elem. Math. 15 (1960), 73-74. MR 0117201 (22:7983)
  • 22. R. J. Simpson and Doron Zeilberger, Necessary conditions for distinct covering systems with square-free moduli, Acta Arith. 59 (1991), no. 1, 59-70. MR 1133237 (92i:11014)
  • 23. L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time: Preliminary report, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, 1973, pp. 1-9. MR 0418518 (54:6557)
  • 24. J. D. Swift, Sets of covering congruences, Bull. Amer. Math. Soc. 60 (1954), 390.
  • 25. Štefan Znám, A survey of covering systems of congruences, Acta Math. Univ. Comenian. 40(41) (1982), 59-79. MR 686961 (84e:10004)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B25, 11A07, 11B75

Retrieve articles in all journals with MSC (2000): 11B25, 11A07, 11B75

Additional Information

Donald Jason Gibson
Affiliation: Eastern Kentucky University, 313 Wallace Building, 521 Lancaster Avenue, Richmond, Kentucky 40475-3102

Received by editor(s): August 27, 2007
Received by editor(s) in revised form: February 23, 2008
Published electronically: September 10, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society