## A covering system with least modulus 25

HTML articles powered by AMS MathViewer

- by Donald Jason Gibson PDF
- Math. Comp.
**78**(2009), 1127-1146 Request permission

## 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

- 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**, DOI 10.4064/aa-48-1-73-79 - S. L. G. Choi,
*Covering the set of integers by congruence classes of distinct moduli*, Math. Comp.**25**(1971), 885–895. MR**297692**, DOI 10.1090/S0025-5718-1971-0297692-7 - R. F. Churchhouse,
*Covering sets and systems of congruences*, Computers in Mathematical Research, North-Holland, Amsterdam, 1968, pp. 20–36. MR**0240045** - P. Erdös,
*On integers of the form $2^k+p$ and some related problems*, Summa Brasil. Math.**2**(1950), 113–123. MR**44558** - P. Erdős,
*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**, DOI 10.1007/BFb0075752 - 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** - 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** - 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. MR**2276778**, DOI 10.1090/S0894-0347-06-00549-2 - Donald Jason Gibson,
*Covering systems*, Ph.D. thesis, University of Illinois, Urbana-Champaign, 2006. - 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**, DOI 10.1016/j.aam.2005.01.004 - Richard K. Guy,
*Unsolved problems in number theory*, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR**2076335**, DOI 10.1007/978-0-387-26677-0 - Ivan Korec and Štefan Znám,
*On disjoint covering of groups by their cosets*, Math. Slovaca**27**(1977), no. 1, 3–7 (English, with Russian summary). MR**485421** - C. E. Krukenberg,
*Covering sets of the integers*, Ph.D. thesis, University of Illinois, Urbana-Champaign, 1971. - Ryozo Morikawa,
*On a method to construct covering sets*, Bull. Fac. Liberal Arts Nagasaki Univ.**22**(1981), no. 1, 1–11. MR**639636** - Ryozo Morikawa,
*Some examples of covering sets*, Bull. Fac. Liberal Arts Nagasaki Univ.**21**(1981), no. 2, 1–4. MR**639635** - Pace Nielsen,
*A covering system whose smallest modulus is large*, preprint. - Š. 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** - N. P. Romanoff,
*Über einige Sätze der additiven Zahlentheorie*, Math. Ann.**109**(1934), no. 1, 668–678 (German). MR**1512916**, DOI 10.1007/BF01449161 - A. Schinzel,
*Reducibility of polynomials and covering systems of congruences*, Acta Arith.**13**(1967/68), 91–101. MR**219515**, DOI 10.4064/aa-13-1-91-101 - J. Schönheim,
*Covering congruences related to modular arithmetic and error correcting codes*, Ars Combin.**16**(1983), no. B, 21–25. MR**737106** - W. Sierpiński,
*Sur un problème concernant les nombres $k\cdot 2^{n}+1$*, Elem. Math.**15**(1960), 73–74 (French). MR**117201** - 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**, DOI 10.4064/aa-59-1-59-70 - 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** - J. D. Swift,
*Sets of covering congruences*, Bull. Amer. Math. Soc.**60**(1954), 390. - Štefan Znám,
*A survey of covering systems of congruences*, Acta Math. Univ. Comenian.**40/41**(1982), 59–79 (English, with Russian and Slovak summaries). MR**686961**

## 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
- © Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**78**(2009), 1127-1146 - MSC (2000): Primary 11B25; Secondary 11A07, 11B75
- DOI: https://doi.org/10.1090/S0025-5718-08-02154-6
- MathSciNet review: 2476575