Covering systems with odd moduli
1]Joshua<EMAIL_ADDRESS>2]Yewen<EMAIL_ADDRESS>3]Tony W. H<EMAIL_ADDRESS>[1]Department of Mathematics, Cedar Crest College
[2]Department of Mathematics, University of California, Santa Barbara
[3]Department of Mathematics, Kutztown University of Pennsylvania

The concept of a covering system was first introduced by Erdős in 1950.  Since their introduction, a lot of the research regarding covering systems has focused on the existence of covering systems with certain restrictions on the moduli.  Arguably, the most famous open question regarding covering systems is the odd covering problem.  In this paper, we explore a variation of the odd covering problem, allowing a single odd prime to appear as a modulus in the covering more than once, while all other moduli are distinct, odd, and greater than $1$.  We also consider this variation while further requiring the moduli of the covering system to be square-free.

MSC: 11A07.

Keywords: Covering system, odd covering.

§ INTRODUCTION

In 1950, Erdős [1] introduced the concept of a covering system of the integers, which is defined as follows.

A covering system of the integers is a finite collection of congruences such that every integer satisfies at least one of the congruences in the collection.

Since their introduction, the existence of certain types of covering systems and their applications has been the investigation of many articles [2, 3, 4, 5, 6, 7, 11, 13, 14, 15].  Of particular interest to the investigation of this paper is the speculative existence of an odd covering.  The following is a well known question, originally asked by Erdős.

[The Odd Covering Problem]
Does there exist a covering system of the integers whose moduli are all odd, distinct, and greater than 1?

If the answer to this question is yes, then such a covering system would be called an odd covering system of the integers.  Hough and Nielsen [12] showed in 2019 that if the moduli of a covering system are distinct and greater than 1, then at least one of the moduli of the system must be divisible by either $2$ or $3$.

If an odd covering exists such that all moduli of the system are square-free, then we refer to this as a square-free odd covering system of the integers.  In 2005, Guo and Sun [8] showed that the lowest common multiple of all moduli in a square-free odd covering system (if it exists) must have at least 22 distinct prime factors.

In 2015, Harrington [10] posed the following question related to the odd covering problem.

Given an odd integer $n\geq 3$, does there exist a covering system of the integers that has $n$ as a modulus at most twice, such that all other moduli are odd, distinct, and greater than 1?

Harrington answered this question in the affirmative when $n=3$ in the same paper.  The following more general question was later asked by Hammer, Harrington, and Marotta [9] in 2018.

Given a fixed odd prime $p$, what is the smallest nonnegative integer $t_p$ for which there exists a covering system of the integers that has $p$ as a modulus exactly $t_p$ times, such that all other moduli are odd, distinct, and greater than 1?

If an odd covering system of the integers exists, then the answer to Question <ref> is that $t_p\leq 1$ for all odd primes $p$.  Harrington's result yields $t_3\leq 2$ and Hammer, Harrington, and Marotta showed that $t_5\leq 3$.  One may further ask a similar question regarding square-free odd coverings.

Given a fixed odd prime $p$, what is the smallest nonnegative integer $\tau_p$ for which there exists a covering system of the integers that has $p$ as a modulus exactly $\tau_p$ times, such that all other moduli are odd, distinct, square-free, and greater than 1?

In Theorem <ref> of Section <ref>, we establish that if $\tau_p\leq 2$ for any odd prime $p$, then there exists an odd covering of the integers.  We also show in Section <ref> that $\tau_7\leq 6$.  In Section <ref>, we show that $t_7\leq 4$, $t_{11}\leq 7$, and $t_p\leq p-5$ for all primes $p\geq23$.  We conclude our investigation in Section <ref> by introducing a lemma that allows us to generalize the main results in Sections <ref> and <ref>.

§ CONDENSED TREE DIAGRAM AND NOTATION

We will adopt the notation used in [5].  Given lists $[r_1,r_2,\ldots,r_k]$ and $[m_1,m_2,\ldots,m_k]$ with $m_1,m_2\ldots,m_k$ pairwise relatively prime positive integers, we let

denote the congruence system $x\equiv\mod{r_j}{m_j}$, $1\leq j\leq k$. By the Chinese Remainder Theorem, this congruence system is equivalent to the congruence $x\equiv\mod{r}{m}$, where $m=m_1m_2\cdots m_k$ and $r\in\{0,1,\dotsc,m-1\}$. Hence, we sometimes also refer to this congruence system as simply a congruence. With this notation, we provide the following example of a covering system.

\begin{equation}\label{eq:example}\begin{gathered}
([1],[2]),\ ([0,1],[2,3]),\ ([0,2],[2,3]),\ ([0,3],[2,9]),\\
([0,0,0],[2,9,5]),\ ([0,0,1],[2,9,5]),\ ([0,0,2],[2,9,5]),\ ([0,0,3],[2,9,5]),\ ([0,0,4],[2,9,5]),\\
([0,6,0],[2,9,5]),\ ([0,6,1],[2,9,5]),\ ([0,6,2],[2,9,5]),\ ([0,6,3],[2,9,5]),\ ([0,6,4],[2,9,5]).
\end{gathered}\end{equation}

This is a covering system since we first cover all integers that are congruent to $1$ modulo $2$ with $([1],[2])$, then all integers congruent to $0$ modulo $2$ are split into congruence classes $0,1,2$ modulo $3$, covered by $([0,0],[2,3])$, $([0,1],[2,3])$, $([0,2],[2,3])$. The congruences $([0,1],[2,3])$ and $([0,2],[2,3])$ are explicit in (<ref>), while integers covered by $([0,0],[2,3])$ are further split into congruence classes $0,3,6$ modulo $9$, covered by $([0,0],[2,9])$, $([0,3],[2,9])$, $([0,6],[2,9])$. Once again, the congruence $([0,3],[2,9])$ is explicit in (<ref>), while integers covered by each of $([0,0],[2,9])$ and $([0,6],[2,9])$ are split into $0,1,2,3,4$ modulo $5$.

The covering system given in (<ref>), however, has many repeated moduli. To eliminate repeated moduli, we forgo some of the congruences inside a congruence system. For example, we forgo $\mod{0}{2}$ in $([0,1],[2,3])$ and write it as $([1],[3])$, and we forgo $\mod{0}{2}$ and $\mod{0}{9}$ in $([0,0,0],[2,9,5])$ to get $([0],[5])$. When we forgo some congruences inside a congruence system, the set of integers covered by the new congruence system is a superset of the original one. Hence, the covering system given by (<ref>) can be modified to obtain the following covering system.

\begin{equation}\label{eq:example2}\begin{gathered}
([1],[2]),\quad ([1],[3]),\quad ([0,2],[2,3]),\quad ([3],[9]),\\
([0],[5]),\quad ([0,1],[2,5]),\quad ([0,2],[3,5]),\quad ([0,0,3],[2,3,5]),\quad ([0,4],[9,5]),\\
([0],[5]),\quad ([0,1],[2,5]),\quad ([0,2],[3,5]),\quad ([0,0,3],[2,3,5]),\quad ([0,6,4],[2,9,5]).
\end{gathered}\end{equation}

Notice that several congruence systems are repeated in (<ref>), thus we can simplify the covering system as follows.

\begin{equation*}\label{eq:example3}\begin{gathered}
([1],[2]),\quad ([1],[3]),\quad ([0,2],[2,3]),\quad ([3],[9]),\quad ([0],[5]),\\
([0,1],[2,5]),\quad ([0,2],[3,5]),\quad ([0,0,3],[2,3,5]),\quad ([0,4],[9,5]),\quad ([0,6,4],[2,9,5]).
\end{gathered}\end{equation*}

This corresponds to the following set of congruences.

\begin{equation}\label{eq:example4}
\begin{gathered}
\mod{1}{2},\quad \mod{1}{3},\quad \mod{2}{6},\quad \mod{3}{9},\quad \mod{0}{5},\\
\mod{6}{10},\quad \mod{12}{15},\quad \mod{18}{30},\quad \mod{9}{45},\quad \mod{24}{90}.
\end{gathered}\end{equation}

To visualize the covering system given by (<ref>), we represent the process of splitting integers into congruence classes using a tree diagram, as illustrated in Figure <ref>. We refer to the node at the top as the root, and the nodes with no further branches below as the leaves. The congruences given at the leaves of this tree come from (<ref>).

(-1.075,-0.35)node[rotate=atan(1/2)]$\footnotesize\substack{([0],[2])}$;(1.075,-0.35) node [rotate=atan(-1/2)]$\footnotesize\substack{([1],[2])}$;
(-3.25,-1.75)node[rotate=atan(3/4)]$\footnotesize\substack{([0,0],[2,3])}$;(-2.15,-1.85)node[rotate=90]$\footnotesize\substack{([0,1],[2,3])}$;(-0.75,-1.75) node [rotate=atan(-3/4)]$\footnotesize\substack{([0,2],[2,3])}$;

A tree diagram of a covering system showing all moduli and residues

(-1.075,-0.35)node[rotate=atan(1/2)]$\footnotesize\substack{\mod{0}{2}}$;(1.075,-0.35) node [rotate=atan(-1/2)]$\footnotesize\substack{\mod{1}{2}}$;
(-3.075,-1.35)node[rotate=atan(1/2)]$\footnotesize\substack{\mod{0}{3}}$;(-2.18,-1.5)node[rotate=90]$\footnotesize\substack{\mod{1}{3}}$;(-0.875,-1.35) node [rotate=atan(-1/2)]$\footnotesize\substack{\mod{2}{3}}$;

A tree diagram of a covering system showing all moduli and residues

The branches immediately below a node in the tree diagram are called the child branches of that node. At each non-leaf node, the number of child branches is always given by a prime number $p$, and we refer to such a node as a $p$-node. Each $p$-node represents a certain subset $S$ of the integers, and its child branches represent a partition of $S$ into congruence classes modulo $p^\alpha m'$ for some positive integers $\alpha$ and $m'$, where $\alpha$ is equal to the number of $p$-nodes along the path from the root and $p\nmid m'$. If the $p$-node represents the subset of integers satisfying the congruence $([r,r'],[p^{\alpha-1},m'])$, then we arrange the congruences such that $([r,r'],[p^\alpha,m'])$, $([r+p^{\alpha-1},r'],[p^\alpha,m'])$, $([r+2p^{\alpha-1},r'],[p^\alpha,m'])$, $\dotsc$, $([r+(p-1)p^{\alpha-1},r'],[p^\alpha,m'])$ are placed from left to right among the child branches. In other words, the congruences on the branches are implied by the positioning of the branches and thus can be omitted from the diagram, as illustrated in Figure <ref>.

A tree diagram of a covering system with congruences on the branches omitted

Next, consider a fixed leaf in the tree diagram. Recall that the congruence is originally obtained by combining all congruences along the path from the root using the Chinese Remainder Theorem. We then choose a subset of these congruences along the path to form the congruence displayed at the leaf. Note that the residue in this congruence is implied by the modulus of the leaf since the factors in the modulus determine which congruences along the path were used. Hence, the residue at the leaf can also be omitted from the diagram, as illustrated in Figure <ref>.

A tree diagram of a covering system showing only the moduli

Continuing to simplify the tree diagram, if the moduli at several leaves branching from a node share the same factor $m_0$, then we can merge them to form a wedge, and we write $\{m_1,m_2,\dotsc,m_k\}\times m_0$ to indicate $2^k$ moduli, given by the product of any subset of $\{m_1,m_2,\dotsc,m_k\}$ together with $m_0$. These congruences are arranged so that they increase in magnitude from left to right among the child branches. This allows us to obtain a condensed tree diagram in Figure <ref>.

(-2,-1)–(0,-1.25)–(-0.25,-1.5)–cycle;[right]at(-0.125,-1.375)$\substack{\{2\}\times3\\2\text{ branches}}$;(-2,-1)–(-2,-2);
(-4,-3)–(-6,-3.25)–(-5.75,-3.5)–cycle;[left]at(-6,-3.375)$\substack{\{2,3\}\times5\\4\text{ branches}}$;(-4,-3)–(-4,-4);[below]at(-4,-4)$\substack{3^2\times5}$;
(2,-3)–(0,-3.25)–(0.25,-3.5)–cycle;[left]at(0,-3.375)$\substack{\{2,3\}\times5\\4\text{ branches}}$;(2,-3)–(2,-4);[below]at(2,-4)$\substack{2\times3^2\times5}$;

A condensed tree diagram of the covering system given by (<ref>)

To illustrate a common technique used when building covering systems of the integers, we now turn our attention to a different system. Let $p>3$ be a prime and consider the following tree diagram.

(4-2*ı,-2-ı)–(3.875-2*ı,-3-ı)–(4.125-2*ı,-3-ı)–cycle;[below]at(4-2*ı,-3-ı)$\substack{\{3\}\times2^2\\2\text{ branches}}$;

(4-2*ı,-2-ı)–(3.875-2*ı,-3-ı)–(4.125-2*ı,-3-ı)–cycle;[below]at(4-2*ı,-3-ı)$\substack{\{3^\j\}\times2^2\\2\text{ branches}}$;

A condensed tree diagram of a covering system whose smallest modulus is $3$

In Figure <ref>, note that the structure of the subtree given in
Figure <ref> is repeated for $i\in\{1,2,\dotsc,p-1\}$. As we consistently split the leftmost node to attach a repeated subtree, we call the leftmost branch from the root a “power branch" of the tree, and condense it as in Figure <ref>. To convert Figure <ref> back to Figure <ref>, the $i$-th repeated subtree is obtained by substituting every factor of $3$ in the first repeated subtree with $3^i$ for $2\leq i\leq p-1$.

(4,-2)–(3.875,-3)–(4.125,-3)–cycle;[below]at(4,-3)$\substack{\{3^i\}\times2^2\\2\text{ branches}}$;

Repeated subtree from Figure <ref>

(4,-2)–(3.875,-3)–(4.125,-3)–cycle;[below]at(4,-3)$\substack{\{3\}\times2^2\\2\text{ branches}}$;
[ultra thick,-latex](0,0)–(-2,-1);[below]at(-2,-1)$\substack{3^2,3^3,\dotsc,3^{p-1}}$;

A tree diagram using a “power branch" notation

We will use tree diagrams similar to Figure <ref> throughout the rest of this paper to denote various covering systems.

§ INVESTIGATING QUESTION <REF>

To begin our investigation for square-free covering systems of the integers, we first provide the following lemma, originally given by Filaseta and Harvey [6].

Let $d$ be an integer.  Given a covering system $\mathcal{C}=\{\mod{r_j}{m_j}: 1\leq j\leq k\}$ of $S\subseteq\mathbb{Z}$, the set $\mathcal{C}_
d=\{r_j+d\pmod{m_j}:1\leq j\leq k\}$ is a covering of the set $S_d=\{s+d:s\in S\}$.

To begin our investigation for square-free covering systems of the integers, we first provide the following lemma, originally given by Hammer, Harrington, and Marotta [9].

Let $p$ be a prime and let $r_1$ and $r_2$ be distinct integers with $0\leq r_1,r_2\leq p-1$. Suppose $\mathcal{C}$ is a covering system of the integers such that $\mod{r_1}{p}\in\mathcal{C}$ and $\mod{r_2}{p}\notin\mathcal{C}$. Then there exists a covering system $\mathcal{C}'$ with the same moduli as those of $\mathcal{C}$ such that $\mod{r_2}{p}\in\mathcal{C}'$ and $\mod{r_1}{p}\notin\mathcal{C}'$. Furthermore, if $\mod{r}{p}\in\mathcal{C}$ with $r\not\equiv\mod{r_1}{p}$, then $\mod{r}{p}\in\mathcal{C}'$.

Let $p\geq3$ be a prime. If there exists a covering system of the integers such that all moduli are odd, square-free, and distinct except that $p$ is used exactly twice as a modulus, then there exists an odd covering of the integers.

Suppose that $\mathcal{C}_0$ is a covering system of the integers such that all moduli are odd, square-free, and distinct except that $p$ is used exactly twice as a modulus. By Lemma <ref>, we may assume that $\mod{0}{p}$ and $\mod{1}{p}$ are congruences in $\mathcal{C}_0$. Let $k$ be a nonnegative integer and let $\ell_\xi$ be nonnegative integers for each $2\leq\xi\leq p-1$ such that

\begin{align*}
\mathcal{C}_0&=\{\mod{0}{p},\mod{1}{p}\}\cup\{\mod{r_j}{m_j}:1\leq j\leq k\}\cup\\
&\hspace{20pt}\bigcup_{\xi=2}^{p-1}\{\mod{r_{\xi,j}}{pm_{\xi,j}}:1\leq j\leq\ell_\xi\},
\end{align*}

where $p\nmid m_j$ for all $1\leq j\leq k$, and $p\nmid m_{\xi,j}$ and $r_{\xi,j}\equiv\mod{\xi}{p}$ for all $1\leq j\leq k_\xi$ and $2\leq\xi\leq p-1$.

We claim that for each $2\leq\xi\leq p-1$, the set of congruences

$$\mathcal{C}_\xi=\{\mod{r_j}{m_j}:1\leq j\leq k\}\cup\{\mod{r_{\xi,j}}{m_{\xi,j}}:1\leq j\leq\ell_\xi\}$$

forms a covering system of the integers. To see this, consider any integer $r$. Let

$$m=\lcm\big(\{m_j:1\leq j\leq k\}\cup\{m_{\xi,j}:1\leq j\leq\ell_\xi\}\big)$$

and let $n$ be an integer that satisfies the congruence system

\end{cases}$$

Since $\mathcal{C}_0$ is a covering system of the integers, $n$ must satisfy one of the congruences in

\{\mod{r_j}{m_j}:1\leq j\leq k\}\cup\{\mod{r_{\xi,j}}{pm_{\xi,j}}:1\leq j\leq\ell_\xi\}.$$

As a result, if $n\equiv\mod{r_{\tilde{j}}}{m_{\tilde{j}}}$ for some $1\leq\tilde{j}\leq k$, then

$$r\equiv n\equiv\mod{r_{\tilde{j}}}{m_{\tilde{j}}};$$

if $n\equiv\mod{r_{\xi,\tilde{j}}}{pm_{\xi,\tilde{j}}}$ for some $1\leq\tilde{j}\leq\ell_\xi$, then

$$r\equiv n\equiv\mod{r_{\xi,\tilde{j}}}{m_{\xi,\tilde{j}}}.$$

This completes the proof of our claim.

Let $q$ be an odd prime such that $q\nmid pm$. For each $1\leq i\leq q-2$, $2\leq\xi\leq p-2$, and $1\leq j\leq\ell_\xi$, let $r_{\xi,i,j}$ be an integer that satisfies the congruence system

r_{\xi,i,j}\equiv\mod{\xi\cdot p^i}{p^{i+1}},\\
\end{cases}$$

Moreover, for each $0\leq i\leq q-1$, let $s_i$ be an integer that satisfies the congruence system

\end{cases}$$

Now, we are ready to build an odd covering system based on the existence of $\mathcal{C}_0$. Consider

\begin{align*}
\mathcal{C}&=\{\mod{p^i}{p^{i+1}}:0\leq i\leq q-2\}\cup\{\mod{s_i}{p^iq}:0\leq i\leq q-1\}\\
&\hspace{20pt}\cup\{\mod{r_j}{m_j}:1\leq j\leq k\}\cup\bigcup_{\xi=2}^{p-1}\{\mod{r_{\xi,i,j}}{p^{i+1}m_{\xi,j}}:0\leq i\leq q-2,1\leq j\leq\ell_\xi\}.
\end{align*}

It is easy to see that all moduli of $\mathcal{C}$ are odd and distinct. To show that $\mathcal{C}$ is a covering system of the integers, let $N$ be an arbitrary integer, and let $i_0$ be the maximum integer such that $p^{i_0}\mid N$. If $0\leq i_0\leq q-2$, then either $N\equiv\mod{p^{i_0}}{p^{i_0+1}}$, which is trivially covered by $\mathcal{C}$, or $N\equiv\mod{\xi\cdot p^{i_0}}{p^{i_0+1}}$ for some $2\leq\xi\leq p-1$, which is covered by

$$\{\mod{r_j}{m_j}:1\leq j\leq k\}\cup\{\mod{r_{\xi,i_0,j}}{p^{i_0+1}m_{\xi,j}}:1\leq j\leq\ell_\xi\}$$

since $C_\xi$ is a covering system of the integers. Lastly, if $i_0\geq q-1$, then $N$ is covered by $\{\mod{s_i}{p^iq}:0\leq i\leq q-1\}$.

The proof of Theorem <ref> can be summarized as a transformation between two tree diagrams. Consider a tree diagram for $\mathcal{C}_0$ as shown in Figure <ref>. In this tree diagram, the root is a $p$-node, and for each $i\in\{2,3,\dotsc,p-1\}$, $T_i$ denotes the subtree below the node that corresponds to the congruence $\mod{i}{p}$. If we replace the leftmost branch by a power branch $p^2,p^3,\dotsc,p^{q-1}$, as shown in Figure <ref>, then the resultant tree diagram represents a covering system $\mathcal{C}$ with odd and distinct moduli that are greater than $1$.

[count=ȷ]ıin-2,-1,0,1,3(0,0)–(ı,-1);[very thick,loosely dotted](1.5,-1)–(2.5,-1);

The root of a tree diagram for $\mathcal{C}_0$

[ultra thick,-latex](0,0)–(-2,-1);[count=ȷ]ıin-1,0,1,3(0,0)–(ı,-1);[very thick,loosely dotted](1.5,-1)–(2.5,-1);

The root of a tree diagram for $\mathcal{C}$

We note that Theorem <ref> can be restated as follows: if $\tau_p\leq2$ for any prime $p\geq3$, then there is an odd covering system of the integers. Hence, to investigate the existence of an odd covering system, one possible approach is to give bounds on $\tau_p$ for an odd prime $p$. In the following, we show that $\tau_7\leq6$.

There exists a covering system of the integers such that all moduli are odd, square-free, and distinct except that $7$ is used exactly six times as a modulus.

Figure <ref> shows a tree diagram for a covering system of the integers such that all moduli are odd, square-free, and distinct except that $7$ is used exactly six times as a modulus. In the tree diagram, note that at the wedge $\{7,3,5,11\}\times13$, there are $16$ available moduli according to the discussions in Section <ref>, but there are only $13$ branches since it is a $13$-node. Thus, we are going to choose the $13$ smallest moduli given by the product of subsets of $\{7,3,5,11\}$ with $13$ among the child branches. Similar situations occurs at a few other wedges, as indicated in the figure.

[right]at(2,-0.375)$\substack{7,7,7,7,7,7\\6\text{ branches}}$;
[right]at(2,-1.375)$\substack{\{7\}\times3\\2\text{ branches}}$;
[right]at(2,-2.375)$\substack{\{7,3\}\times5\\4\text{ branches}}$;
[right]at(2,-3.375)$\substack{\{7,3,5\}\times11\\8\text{ branches}}$;
[below]at(-4,-6.5)$\substack{\{7,3,5,11\}\times13\\16\text{ available moduli}\\\text{to cover }13\text{ branches}}$;
[right]at(6,-5.375)$\substack{\{7,3,5,11\}\times19\\16\text{ branches}}$;
[below]at(-1,-7.5)$\substack{\{7,3,5,11\}\times17\times13\\16\text{ available moduli}\\\text{to cover }13\text{ branches}}$;
[below]at(0.75,-5.5)$\substack{\{7,3,5,11\}\times17\\16\text{ branches}}$;
[below]at(2,-7.5)$\substack{\{7,3,5,11\}\times19\times13\\16\text{ available moduli}\\\text{to cover }13\text{ branches}}$;
[below]at(5.25,-6.5)$\substack{\{7,3,5,11\}\times19\times17\\16\text{ branches}}$;
[below]at(4,-9)$\substack{\{7,3,5,11\}\times19\times17\times13\\16\text{ available moduli}\\\text{to cover }13\text{ branches}}$;
[below]at(6.5,-7.5)$\substack{\{7,3,5,11,19\}\times23\\32\text{ available moduli}\\\text{to cover }23\text{ branches}}$;

Square-free odd covering with $7$ used exactly six times as a modulus

§ INVESTIGATING QUESTION <REF>

In this section, we establish upper bounds for $t_p$ for all odd primes $p$.  We begin by showing that $t_7\leq 4.$

There exists a covering system of the integers such that all moduli are odd and distinct except that $7$ is used exactly four times as a modulus.

The tree diagram of this covering system is given by Figure <ref>, where subtrees $T_1$ to $T_6$ are given in Figures <ref> to <ref>, respectively. Here, $q>19$ is a prime.

Please take special note in the power branch $7^3,7^4,\dotsc,7^{q-1}$ in Figure <ref>. Here, the repeated subtrees are obtained by substituting every factor of $7^2$ (but not $7$) in the first repeated subtree with $7^i$ for $3\leq i\leq q-1$.

[above]at(2,-0.2)$\substack{7,7,7,7\\4\text{ branches}}$;
(0,0)–(-5,-1)–(-6.125,-2)–(-5.875,-2)–(-5,-1);[ultra thick,-latex](-5,-1)–(-7,-2);
[above]at(-7,-1.7)$\substack{3^2,3^3,\dotsc,3^{q-1}}$;[below]at(-6,-2)$\substack{\{7\}\times3\\2\text{ branches}}$;

(0,0)–(-2,-1)–(-3,-2);[ultra thick,-latex](-2,-1)–(-4,-2);
(-2,-1)–(-2,-2)–(-2.125,-3)–(-1.875,-3)–(-2,-2);[ultra thick,-latex](-2,-2)–(-4,-3);
[below]at(-4,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(-2,-3)$\substack{\{7,3\}\times5\\4\text{ branches}}$;

(0,0)–(2,-1)–(1,-2);[ultra thick,-latex](2,-1)–(0,-2);
(2,-1)–(2.5,-2)–(1.625,-3)–(1.875,-3)–(2.5,-2);[ultra thick,-latex](2.5,-2)–(0.5,-3);
[below]at(0.2,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(1.75,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

Odd covering with $7$ used exactly four times as a modulus

[ultra thick,-latex](0,0)–(-8,-1);[below]at(-8.3,-1)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
(0,0)–(-6.5,-1)–(-6,-1)–(0,0);[below]at(-6.25,-1)$\substack{\{7,3\}\times11\\4\text{ branches}}$;
(0,0)–(-4.5,-1)–(-4,-1)–(0,0);[below]at(-4.25,-1)$\substack{\{7,3\}\times5\times11\\4\text{ branches}}$;
(0,0)–(-2,-1);[ultra thick,-latex](-2,-1)–(-4,-2);[below]at(-4.7,-2)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(-2,-1)–(-2.625,-2)–(-2.375,-2)–(-2,-1);[below]at(-2.5,-2)$\substack{\{7,3,5\}\times17\\8\text{ branches}}$;
(-2,-1)–(-0.625,-2)–(-0.375,-2)–(-2,-1);[below]at(-0.5,-2)$\substack{\{7,3,5\}\times11\times17\\8\text{ branches}}$;
(0,0)–(3,-1);[ultra thick,-latex](3,-1)–(1,-2);[above]at(0.9,-1.7)$\substack{19^2,19^3,\dotsc,19^{q-1}}$;
(3,-1)–(2.375,-2)–(2.625,-2)–(3,-1);[below]at(2.5,-2)$\substack{\{7,3,5\}\times19\\8\text{ branches}}$;
(3,-1)–(4.375,-2)–(4.625,-2)–(3,-1);[below]at(4.5,-2)$\substack{\{7,3,5\}\times11\times19\\8\text{ branches}}$;

$T_1$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(0,0)–(-1.125,-1)–(-0.875,-1)–(0,0);[below]at(-1,-1)$\substack{\{7,3,5\}\times17\\8\text{ branches}}$;
(0,0)–(0.575,-1)–(0.825,-1)–(0,0);[below]at(0.7,-1)$\substack{\{7,3,5\}\\\times19\times17\\8\text{ branches}}$;

$T_3$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(0,0)–(-1.125,-1)–(-0.875,-1)–(0,0);[below]at(-1,-1)$\substack{\{7,3,5\}\times17\\8\text{ branches}}$;
(0,0)–(0.875,-1)–(1.125,-1)–(0,0);[below]at(1,-1)$\substack{\{7,3,5\}\\\times11\times19\times17\\8\text{ branches}}$;

$T_4$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8,-1);[below]at(-8.3,-1)$\substack{7^3,7^4,\dotsc,7^{q-1}}$;
(0,0)–(-6.5,-1)–(-6,-1)–(0,0);[below]at(-6.25,-1)$\substack{\{3,5\}\times7^2\\4\text{ branches}}$;

(0,0)–(-4,-1);[ultra thick,-latex](-4,-1)–(-6,-2);[below]at(-6.6,-2)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(-4,-1)–(-4.625,-2)–(-4.375,-2)–(-4,-1);[below]at(-4.5,-2)$\substack{\{7,3,5\}\times13\\8\text{ branches}}$;
(-4,-1)–(-2.625,-2)–(-2.375,-2)–(-4,-1);[below]at(-2.5,-2)$\substack{\{3,5\}\times7^2\times13\\4\text{ branches}}$;

(0,0)–(1,-1);[ultra thick,-latex](1,-1)–(-1,-2);[above]at(-1.2,-1.7)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
(1,-1)–(0.375,-2)–(0.625,-2)–(1,-1);[below]at(0.5,-2)$\substack{\{7,3\}\times11\\4\text{ branches}}$;
(1,-1)–(2.375,-2)–(2.625,-2)–(1,-1);[below]at(2.5,-2)$\substack{\{3,5\}\times7^2\times11\\4\text{ branches}}$;

$T_2$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(0,0)–(-0.625,-1)–(-0.375,-1)–(0,0);[below]at(-0.5,-1)$\substack{\{7,3,5\}\times13\\8\text{ branches}}$;
(0,0)–(1.375,-1)–(1.625,-1)–(0,0);[below]at(1.5,-1)$\substack{\{7,3\}\times11\times13\\4\text{ branches}}$;

$T_5$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(0,0)–(-0.625,-1)–(-0.375,-1)–(0,0);[below]at(-0.5,-1)$\substack{\{7,3,5\}\times13\\8\text{ branches}}$;
(0,0)–(1.875,-1)–(2.125,-1)–(0,0);[below]at(2,-1)$\substack{\{7,3\}\times5\times11\times13\\4\text{ branches}}$;

$T_6$ in Figure <ref>

Next, we show that $t_{11}\leq 7$.

There exists a covering system of the integers such that all moduli are odd and distinct except that $11$ is used exactly seven times as a modulus.

The tree diagram of this covering system is given by Figure <ref>, where subtrees $T_1$ to $T_4$ are given in Figures <ref> to <ref>, respectively.  Here, $q>19$ is a prime.

[above]at(2,-0.2)$\substack{11,11,11,11,11,11,11\\7\text{ branches}}$;
(0,0)–(-8,-1)–(-9.125,-2)–(-8.875,-2)–(-8,-1);[ultra thick,-latex](-8,-1)–(-10,-2);
[above]at(-10,-1.7)$\substack{3^2,3^3,\dotsc,3^{q-1}}$;[below]at(-9,-2)$\substack{\{11\}\times3\\2\text{ branches}}$;

(0,0)–(-5,-1)–(-6.5,-2);[ultra thick,-latex](-5,-1)–(-7,-2);
(-5,-1)–(-5.5,-2)–(-6.625,-3)–(-6.375,-3)–(-5.5,-2);[ultra thick,-latex](-5.5,-2)–(-7.5,-3);
[below]at(-8.3,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(-6.5,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

(0,0)–(-1.5,-1)–(-2.5,-2);[ultra thick,-latex](-1.5,-1)–(-3.5,-2);
(-1.5,-1)–(-1,-2)–(-2.125,-3)–(-1.875,-3)–(-1,-2);[ultra thick,-latex](-1,-2)–(-3,-3);
[above]at(-3.3,-2.9)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(-2,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

(0,0)–(3,-1)–(2,-2);[ultra thick,-latex](3,-1)–(1,-2);
(3,-1)–(3.5,-2)–(2.625,-3)–(2.875,-3)–(3.5,-2);[ultra thick,-latex](3.5,-2)–(1.5,-3);
[above]at(1.2,-2.9)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(2.75,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

Odd covering with $11$ used exactly seven times as a modulus

[ultra thick,-latex](0,0)–(-8,-1);[below]at(-8.3,-1)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-6.5,-1)–(-6,-1)–(0,0);[below]at(-6.25,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;
(0,0)–(-4.5,-1)–(-4,-1)–(0,0);[below]at(-4.25,-1)$\substack{\{3\}\times5\times7\\2\text{ branches}}$;
(0,0)–(-2,-1);[ultra thick,-latex](-2,-1)–(-4,-2);[below]at(-4.7,-2)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(-2,-1)–(-2.625,-2)–(-2.375,-2)–(-2,-1);[below]at(-2.5,-2)$\substack{\{11,3,5\}\times13\\8\text{ branches}}$;
(-2,-1)–(-0.625,-2)–(-0.375,-2)–(-2,-1);[below]at(-0.5,-2)$\substack{\{11,3\}\times7\times13\\4\text{ branches}}$;
(0,0)–(4.7,-1);[ultra thick,-latex](4.7,-1)–(2.7,-2);[below]at(2,-2)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(4.7,-1)–(4.075,-2)–(4.325,-2)–(4.7,-1);[below]at(4.2,-2)$\substack{\{11,3,5\}\times13\\8\text{ branches}}$;
(4.7,-1)–(6.075,-2)–(6.325,-2)–(4.7,-1);[below]at(6.2,-2)$\substack{\{11,3\}\times5\times7\times13\\4\text{ branches}}$;

$T_1$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8,-1);[below]at(-8.3,-1)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-6.5,-1)–(-6,-1)–(0,0);[below]at(-6.25,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;
(0,0)–(-4.5,-1)–(-4,-1)–(0,0);[below]at(-4.25,-1)$\substack{\{3\}\times5\times7\\2\text{ branches}}$;
(0,0)–(-2,-1);[ultra thick,-latex](-2,-1)–(-4,-2);[below]at(-4.4,-2)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(-2,-1)–(-2.125,-2)–(-1.875,-2)–(-2,-1);[below]at(-2,-2)$\substack{\{11,3,5,7\}\times17\\16\text{ branches}}$;

(0,0)–(4,-1);[ultra thick,-latex](4,-1)–(0.5,-2);[above]at(0.3,-1.9)$\substack{19^2,19^3,\dotsc,19^{q-1}}$;
(4,-1)–(6,-1.125)–(5.75,-1.25)–(4,-1);[above]at(6,-1.075)$\substack{\{11,3,5,7\}\times19\\16\text{ branches}}$;
(4,-1)–(2,-2);[ultra thick,-latex](2,-2)–(0,-3);[below]at(-0.7,-3)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(2,-2)–(1.875,-3)–(2.125,-3)–(2,-2);[below]at(2,-3)$\substack{\{11,3,5,7\}\times19\times13\\16\text{ available moduli}\\\text{to cover }12\text{ branches}}$;
(4,-1)–(6.5,-2);[ultra thick,-latex](6.5,-2)–(4.5,-3);[above]at(4.1,-2.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(6.5,-2)–(6.375,-3)–(6.625,-3)–(6.5,-2);[below]at(6.5,-3)$\substack{\{11,3,5,7\}\times19\times17\\16\text{ branches}}$;

$T_2$ in Figure <ref>

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.125,-1)–(-1.875,-1)–(0,0);[below]at(-2,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;
(0,0)–(-0.125,-1)–(0.125,-1)–(0,0);[below]at(0,-1)$\substack{\{3\}\times11\times5\times7\\2\text{ branches}}$;
(0,0)–(1.875,-1)–(2.125,-1)–(0,0);[below]at(2,-1)$\substack{\{3\}\times11\times7\\2\text{ branches}}$;

$T_3$ in Figure <ref>

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.125,-1)–(-1.875,-1)–(0,0);[below]at(-2,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;
(0,0)–(-0.125,-1)–(0.125,-1)–(0,0);[below]at(0,-1)$\substack{\{3\}\times5\times7\\2\text{ branches}}$;
(0,0)–(1.875,-1)–(2.125,-1)–(0,0);[below]at(2,-1)$\substack{\{3\}\times11\times7\\2\text{ branches}}$;

$T_4$ in Figure <ref>

Lastly, we establish that $t_p\leq p-5$ for all primes $p\geq 23$.

Let $p\geq23$ be a prime. There exists a covering system of the integers such that all moduli are odd and distinct except that $p$ is used exactly $p-5$ times as a modulus.

The tree diagram of this covering system is given by Figure <ref>, where subtrees $T_1$ to $T_{11}$ are given in Figures <ref> to <ref>, respectively. Here, $q>19$ and $q\neq p$ is a prime.

[above]at(3,-0.1)$\substack{p,p,\dotsc,p\\p-5\text{ branches}}$;
(0,0)–(-9,-1)–(-10.125,-2)–(-9.875,-2)–(-9,-1);[ultra thick,-latex](-9,-1)–(-11,-2);
[above]at(-11.2,-1.8)$\substack{3^2,3^3,\dotsc,3^{q-1}}$;[below]at(-10,-2)$\substack{\{p\}\times3\\2\text{ branches}}$;

(0,0)–(-5.5,-1)–(-7,-2);[ultra thick,-latex](-5.5,-1)–(-7.5,-2);
(-5.5,-1)–(-6,-2)–(-7.125,-3)–(-6.875,-3)–(-6,-2);[ultra thick,-latex](-6,-2)–(-8,-3);
[below]at(-9,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(-7,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

(0,0)–(-1.5,-1)–(-2.5,-2);[ultra thick,-latex](-1.5,-1)–(-3.5,-2);
(-1.5,-1)–(-1,-2)–(-2.125,-3)–(-1.875,-3)–(-1,-2);[ultra thick,-latex](-1,-2)–(-3,-3);
[above]at(-3.5,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(-2.2,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

(0,0)–(3,-1)–(2,-2);[ultra thick,-latex](3,-1)–(1,-2);
(3,-1)–(3.8,-2)–(2.925,-3)–(3.175,-3)–(3.8,-2);[ultra thick,-latex](3.8,-2)–(1.8,-3);
[above]at(1.3,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(3,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

(0,0)–(7.5,-1)–(6.5,-2);[ultra thick,-latex](7.5,-1)–(5.5,-2);
(7.5,-1)–(8.5,-2)–(7.375,-3)–(7.625,-3)–(8.5,-2);[ultra thick,-latex](8.5,-2)–(6.5,-3);
[above]at(6,-3)$\substack{5^2,5^3,\dotsc,5^{q-1}}$;[below]at(7.5,-3)$\substack{\{3\}\times5\\2\text{ branches}}$;

Odd covering with $p$ ($p\geq23$) used exactly $p-5$ times as a modulus

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.75,-1)–(-2.25,-1)–(0,0);[below]at(-2.5,-1)$\substack{\{3,5\}\times7\\4\text{ branches}}$;
(0,0)–(1,-1)–(-1.125,-2)–(-0.875,-2)–(1,-1)–(0.625,-2)–(0.875,-2)–(1,-1)–(2.375,-2)–(2.625,-2)–(1,-1);[ultra thick,-latex](1,-1)–(-2.5,-2);[below]at(-3.3,-2)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
[below]at(-1,-2)$\substack{\{3,7\}\times5\times11\\4\text{ branches}}$;[below]at(0.75,-2)$\substack{\{3,7\}\times11\\4\text{ branches}}$;[below]at(2.5,-2)$\substack{\{3\}\times p\times5\times11\\2\text{ branches}}$;

$T_1$ in Figure <ref>

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.75,-1)–(-2.25,-1)–(0,0);[below]at(-2.5,-1)$\substack{\{3,5\}\times7\\4\text{ branches}}$;
(0,0)–(1,-1)–(-1.125,-2)–(-0.875,-2)–(1,-1)–(0.625,-2)–(0.875,-2)–(1,-1)–(2.375,-2)–(2.625,-2)–(1,-1);[ultra thick,-latex](1,-1)–(-2.5,-2);[below]at(-3.3,-2)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
[below]at(-1,-2)$\substack{\{3,7\}\times5\times11\\4\text{ branches}}$;[below]at(0.75,-2)$\substack{\{3,7\}\times11\\4\text{ branches}}$;[below]at(2.7,-2)$\substack{\{3\}\times p\times5\times7\times11\\2\text{ branches}}$;

$T_2$ in Figure <ref>

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.75,-1)–(-2.25,-1)–(0,0);[below]at(-2.5,-1)$\substack{\{3,5\}\times7\\4\text{ branches}}$;
(0,0)–(1,-1)–(-1.125,-2)–(-0.875,-2)–(1,-1)–(0.625,-2)–(0.875,-2)–(1,-1)–(2.375,-2)–(2.625,-2)–(1,-1);[ultra thick,-latex](1,-1)–(-2.5,-2);[below]at(-3.3,-2)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
[below]at(-1,-2)$\substack{\{3,7\}\times5\times11\\4\text{ branches}}$;[below]at(0.75,-2)$\substack{\{3,7\}\times11\\4\text{ branches}}$;[below]at(2.5,-2)$\substack{\{3\}\times p\times11\\2\text{ branches}}$;

$T_3$ in Figure <ref>

[ultra thick,-latex](0,0)–(-4,-1);[above]at(-4,-0.8)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-2.75,-1)–(-2.25,-1)–(0,0);[below]at(-2.5,-1)$\substack{\{3,5\}\times7\\4\text{ branches}}$;
(0,0)–(1,-1)–(-1.125,-2)–(-0.875,-2)–(1,-1)–(0.625,-2)–(0.875,-2)–(1,-1)–(2.375,-2)–(2.625,-2)–(1,-1);[ultra thick,-latex](1,-1)–(-2.5,-2);[below]at(-3.3,-2)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
[below]at(-1,-2)$\substack{\{3,7\}\times5\times11\\4\text{ branches}}$;[below]at(0.75,-2)$\substack{\{3,7\}\times11\\4\text{ branches}}$;[below]at(2.5,-2)$\substack{\{3\}\times p\times7\times11\\2\text{ branches}}$;

$T_4$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8,-1);[above]at(-8,-0.9)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-6.8,-1)–(-6.3,-1)–(0,0);[below]at(-6.8,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;

(0,0)–(-5,-1);[ultra thick,-latex](-5,-1)–(-6.5,-2);at(-7.8,-2)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(-5,-1)–(-5.625,-2)–(-5.375,-2)–(-5,-1);[below]at(-5.7,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;
(-5,-1)–(-4.375,-2)–(-4.125,-2)–(-5,-1);[below]at(-4,-2)$\substack{\{3,5\}\times7\times13\\4\text{ branches}}$;

(0,0)–(-1,-1);[ultra thick,-latex](-1,-1)–(-2.8,-2);[above]at(-3.1,-1.7)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;
(-1,-1)–(-1.875,-2)–(-1.625,-2)–(-1,-1);[below]at(-1.9,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;
(-1,-1)–(-0.125,-2)–(0.125,-2)–(-1,-1);[below]at(-0,-2)$\substack{\{3,5\}\times p\times7\times13\\4\text{ branches}}$;

$T_5$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8,-1);[above]at(-8,-0.9)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
(0,0)–(5.25,-1)–(5.75,-1)–(0,0);[below]at(5.6,-1)$\substack{\{3,7\}\times11\\4\text{ branches}}$;
(0,0)–(6.25,-1)–(6.75,-1)–(0,0);[above]at(6.2,-0.9)$\substack{\{3\}\times p\times11\\2\text{ branches}}$;
(0,0)–(-6,-1)–(-7.625,-2)–(-7.375,-2)–(-6,-1)–(-6.125,-2)–(-5.875,-2)–(-6,-1);[ultra thick,-latex](-6,-1)–(-8.3,-2);
[above]at(-8.1,-1.6)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;[below]at(-7.5,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;[below]at(-6,-2)$\substack{\{p,3\}\\\times11\times13\\4\text{ branches}}$;

(0,0)–(-2.5,-1)–(-4.125,-2)–(-3.875,-2)–(-2.5,-1)–(-2.625,-2)–(-2.375,-2)–(-2.5,-1);[ultra thick,-latex](-2.5,-1)–(-4.8,-2);
[above]at(-4.6,-1.6)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;[below]at(-4.2,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;[below]at(-2.5,-2)$\substack{\{p,3\}\\\times5\times11\times13\\4\text{ branches}}$;

(0,0)–(1,-1)–(-0.625,-2)–(-0.375,-2)–(1,-1)–(0.875,-2)–(1.125,-2)–(1,-1);[ultra thick,-latex](1,-1)–(-1.3,-2);
[above]at(-1.1,-1.6)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;[below]at(-0.7,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;[below]at(1,-2)$\substack{\{p,3\}\\\times7\times11\times13\\4\text{ branches}}$;

(0,0)–(4.5,-1)–(2.875,-2)–(3.125,-2)–(4.5,-1)–(4.575,-2)–(4.825,-2)–(4.5,-1);[ultra thick,-latex](4.5,-1)–(2.2,-2);
[above]at(2.4,-1.6)$\substack{13^2,13^3,\dotsc,13^{q-1}}$;[below]at(2.8,-2)$\substack{\{p,3,5\}\times13\\8\text{ branches}}$;[below]at(4.7,-2)$\substack{\{p,3\}\\\times5\times7\times11\times13\\4\text{ branches}}$;

$T_7$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8,-1);[above]at(-8,-0.9)$\substack{7^2,7^3,\dotsc,7^{q-1}}$;
(0,0)–(-6.8,-1)–(-6.3,-1)–(0,0);[below]at(-6.8,-1)$\substack{\{3\}\times7\\2\text{ branches}}$;

(0,0)–(-5,-1);[ultra thick,-latex](-5,-1)–(-6.5,-2);at(-7.8,-2)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(-5,-1)–(-5.725,-2)–(-5.475,-2)–(-5,-1);[below]at(-5.8,-2)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;
(-5,-1)–(-4.375,-2)–(-4.125,-2)–(-5,-1);[below]at(-4,-2)$\substack{\{p,3,5\}\times7\times17\\8\text{ branches}}$;

(0,0)–(-1,-1);[ultra thick,-latex](-1,-1)–(-2.8,-2);[above]at(-3.1,-1.7)$\substack{19^2,19^3,\dotsc,19^{q-1}}$;
(-1,-1)–(-1.875,-2)–(-1.625,-2)–(-1,-1);[below]at(-1.9,-2)$\substack{\{p,3,5\}\times19\\8\text{ branches}}$;
(-1,-1)–(-0.125,-2)–(0.125,-2)–(-1,-1);[below]at(-0,-2)$\substack{\{p,3,5\}\times7\times19\\8\text{ branches}}$;

(-1,-1)–(3.5,-2);[ultra thick,-latex](3.5,-2)–(1.5,-3);[below]at(1,-3)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(3.5,-2)–(3.175,-3)–(3.425,-3)–(3.5,-2);[below]at(3.3,-3)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;
(3.5,-2)–(5.375,-3)–(5.625,-3)–(3.5,-2);[below]at(5.5,-3)$\substack{\{p,3,5\}\times7\times19\times17\\8\text{ branches}}$;

$T_6$ in Figure <ref>

[ultra thick,-latex](0,0)–(-8.3,-1);[above]at(-8,-0.9)$\substack{11^2,11^3,\dotsc,11^{q-1}}$;
(0,0)–(5.25,-1)–(5.75,-1)–(0,0);[below]at(6,-1)$\substack{\{3,7\}\times11\\4\text{ branches}}$;
(0,0)–(6.25,-1)–(6.75,-1)–(0,0);[above]at(6.2,-0.9)$\substack{\{3\}\times p\times7\times11\\2\text{ branches}}$;
(0,0)–(-6.5,-1)–(-8.125,-2)–(-7.875,-2)–(-6.5,-1)–(-6.625,-2)–(-6.375,-2)–(-6.5,-1);[ultra thick,-latex](-6.5,-1)–(-8.8,-2);
[above,rotate=(atan(1/2.3))]at(-8.455,-1.85)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;[below]at(-8,-2)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;[below]at(-6.5,-2)$\substack{\{p,3,5\}\\\times11\times17\\8\text{ branches}}$;

(0,0)–(-3.3,-1)–(-4.925,-2)–(-4.675,-2)–(-3.3,-1)–(-3.425,-2)–(-3.175,-2)–(-3.3,-1);[ultra thick,-latex](-3.3,-1)–(-5.6,-2);
[above,rotate=(atan(1/2.3))]at(-4.83,-1.67)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;[below]at(-4.95,-2)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;[below]at(-3.3,-2)$\substack{\{p,3,5\}\\\times7\times11\times17\\8\text{ branches}}$;

(0,0)–(-0.1,-1)–(-1.725,-2)–(-1.475,-2)–(-0.1,-1)–(-0.225,-2)–(0.025,-2)–(-0.1,-1);[ultra thick,-latex](-0.1,-1)–(-2.4,-2);
[above,rotate=(atan(1/2.3))]at(-1.57,-1.67)$\substack{19^2,19^3,\dotsc,19^{q-1}}$;[below]at(-1.6,-2)$\substack{\{p,3,5\}\times19\\8\text{ branches}}$;[below]at(-0.1,-2)$\substack{\{p,3,5\}\\\times11\times19\\8\text{ branches}}$;

(0,0)–(4.3,-1)–(2.675,-2)–(2.925,-2)–(4.3,-1)–(4.175,-2)–(4.425,-2)–(4.3,-1);[ultra thick,-latex](4.3,-1)–(2,-2);
[above,rotate=(atan(1/2.3))]at(2.675,-1.75)$\substack{19^2,19^3,\dotsc,19^{q-1}}$;[below]at(2.7,-2)$\substack{\{p,3,5\}\times19\\8\text{ branches}}$;[below]at(4.3,-2)$\substack{\{p,3,5\}\\\times7\times11\times19\\8\text{ branches}}$;

$T_8$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(0,0)–(-1.125,-1)–(-0.875,-1)–(0,0);[below]at(-1,-1)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;
(0,0)–(0.575,-1)–(0.825,-1)–(0,0);[below]at(0.7,-1)$\substack{\{p,3,5\}\\\times19\times17\\8\text{ branches}}$;

$T_9$ in Figure <ref> and Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(0,0)–(-1.125,-1)–(-0.875,-1)–(0,0);[below]at(-1,-1)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;
(0,0)–(0.875,-1)–(1.125,-1)–(0,0);[below]at(1,-1)$\substack{\{p,3,5\}\\\times11\times19\times17\\8\text{ branches}}$;

$T_{10}$ in Figure <ref>

[ultra thick,-latex](0,0)–(-2,-1);[above]at(-2.4,-0.8)$\substack{17^2,17^3,\dotsc,17^{q-1}}$;
(0,0)–(-1.125,-1)–(-0.875,-1)–(0,0);[below]at(-1,-1)$\substack{\{p,3,5\}\times17\\8\text{ branches}}$;
(0,0)–(0.875,-1)–(1.125,-1)–(0,0);[below]at(1,-1)$\substack{\{p,3,5\}\\\times7\times11\times19\times17\\8\text{ branches}}$;

$T_{11}$ in Figure <ref>

§ EXTENSION OF RESULTS AND CONCLUDING REMARKS

We can extend Theorems <ref> and <ref> by using the following lemma.

Let $p$ be a prime and $t$ be a positive integer such that $t\leq p$. Let $\mathcal{C}_0$ be a covering system of the integers whose tree diagram is given in Figure $\ref{fig:rootp-node}$, where all moduli are distinct except that $p$ is used exactly $p-t$
times as a modulus, and no modulus of $\mathcal{C}_0$ is divisible by $p^2$.

[count=ȷ]ıin-2,-1,0,2(0,0)–(ı,-1);[very thick,loosely dotted](0.5,-1)–(1.5,-1);
[right]at(2.5,-0.375)$\substack{p,p,\dotsc,p\\p-t\text{ branches}}$;

The root of a tree diagram for $\mathcal{C}_0$

Then for all primes $q>p$, there exists a covering system $\mathcal{C}$ of the integers such that all moduli are distinct except that $q$ is used exactly $q-t$ times as a modulus, and no modulus of $\mathcal{C}$ is divisible by $q^2$. Furthermore, if all moduli of $\mathcal{C}_0$ are odd, then all moduli of $\mathcal{C}$ are odd; if all moduli of $\mathcal{C}_0$ are square-free, then all moduli of $\mathcal{C}$ are square-free.

In the tree diagram of $\mathcal{C}_0$ as shown in Figure <ref>, the root is a $p$-node, and for each $i\in\{0,1,\dotsc,t-1\}$, $T_i$ denotes the subtree below the node that corresponds to the congruence $\mod{i}{p}$. Note that this is the only $p$-node in the tree since no modulus of $\mathcal{C}_0$ is divisible by $p^2$.

To obtain a tree diagram for $\mathcal{C}$, we are going to replace the root of $\mathcal{C}_0$ by a $q$-node as shown in Figure <ref>.

[count=ȷ]ıin-2,-1,0,2(0,0)–(ı,-1);[very thick,loosely dotted](0.5,-1)–(1.5,-1);
[right]at(2.5,-0.375)$\substack{q,q,\dotsc,q\\q-t\text{ branches}}$;

The root of a tree diagram for $\mathcal{C}$

The only difficulty in this root replacement is that it may not be compatible with the existing $q$-nodes in the tree diagram for $\mathcal{C}_0$. To solve this issue, we replace every $q$-node in the tree diagram for $\mathcal{C}_0$ (Figure <ref>) by a $p$-node (Figure <ref>) and keep only the subtrees $T'_i$ for $i\in\{0,1,\dotsc,p-1\}$. Lastly, if a modulus $m$ in $\mathcal{C}_0$ satisfies $m=pr$ such that $p\nmid r$, then the resultant modulus in $\mathcal{C}$ is $qr$; if a modulus $m$ in $\mathcal{C}_0$ satisfies $m=q^\alpha s$ for some positive integer $\alpha$ such that $q\nmid s$, then the resultant modulus in $\mathcal{C}$ is $p^\alpha s$. This completes our construction of a tree diagram for $\mathcal{C}$.

ıin-4,-3,-2,1,4(0,0)–(ı,-1);[very thick,loosely dotted](-1,-1)–(0,-1);[very thick,loosely dotted](2,-1)–(3,-1);

A $q$-node in the tree diagram for $\mathcal{C}_0$

ıin-4,-3,-2,1(0,0)–(ı,-1);[very thick,loosely dotted](-1,-1)–(0,-1);

A $p$-node in the tree diagram for $\mathcal{C}$

Combining Lemma <ref> with Theorem <ref>, we have the following result.

For all primes $p\geq7$, $\tau_p\leq p-1$.

As for the bounds on $t_p$ for primes $p\geq3$, we summarize the results in the following table.

$p$    Upper bound on $t_p$    Sources

$3$    $t_p\leq2=p-1$    [10]

$5$    $t_p\leq3=p-2$    [9]

$7$    $t_p\leq4=p-3$    Theorem <ref>

$11\leq p\leq19$    $t_p\leq p-4$    Theorem <ref> & Lemma <ref>

$p\geq23$    $t_p\leq p-5$    Theorem <ref>

Summary of results regarding Question <ref>

We observe from Table <ref> that there exists a constant $c$ such that for all sufficiently large primes $p$, $t_p\leq p-c$. For future investigation, it is certainly of interest to continue improving on the constant $c$. Nevertheless, it is of greater interest to investigate the following question.

Does there exist a constant $0\leq\epsilon<1$ such that for all sufficiently large primes $p$, $t_p\leq\epsilon p$?

The existence of an odd covering system would imply that we can take $\epsilon=0$ for all sufficiently large primes $p$, thus Question <ref> provides a progressive approach to solving the odd covering problem.

Before we end this paper, we also provide a similar lemma to Lemma <ref>, which could be useful in the future.

Let $p$ be a prime and $t$ be a positive integer such that $t\leq p$. Let $\mathcal{C}_0$ be a covering system of the integers whose tree diagram is given in Figure $\ref{fig:rootp-node2}$, where all moduli are distinct except that $p$ is used exactly $p-t$ times as a modulus.

[count=ȷ]ıin-2,-1,0,2(0,0)–(ı,-1);[very thick,loosely dotted](0.5,-1)–(1.5,-1);
[right]at(2.5,-0.375)$\substack{p,p,\dotsc,p\\p-t\text{ branches}}$;

The root of a tree diagram for $\mathcal{C}_0$

Let $M$ be the least common multiple of all moduli of $\mathcal{C}_0$. Then for all odd primes $q\geq t$ that satisfies $q\nmid M$, there exists a covering system $\mathcal{C}$ of the integers such that all moduli are distinct except that $q$ is used exactly $q-t$ times as a modulus. Furthermore, if all moduli of $\mathcal{C}_0$ are odd, then all moduli of $\mathcal{C}$ are odd; if all moduli of $\mathcal{C}_0$ are square-free, then all moduli of $\mathcal{C}$ are square-free.

In the tree diagram of $\mathcal{C}_0$ as shown in Figure <ref>, the root is a $p$-node, and for each $i\in\{0,1,\dotsc,t-1\}$, $T_i$ denotes the subtree below the node that corresponds to the congruence $\mod{i}{p}$.

To obtain a tree diagram for $\mathcal{C}$, we are going to replace the root of $\mathcal{C}_0$ by a $q$-node as shown in Figure <ref>.

[count=ȷ]ıin-2,-1,0,2(0,0)–(ı,-1);[very thick,loosely dotted](0.5,-1)–(1.5,-1);
[right]at(2.5,-0.375)$\substack{q,q,\dotsc,q\\q-t\text{ branches}}$;

The root of a tree diagram for $\mathcal{C}$

There are no existing $q$-nodes in the tree diagram for $\mathcal{C}_0$, so we do not need to perform any further replacement, and have already obtained a tree diagram for $\mathcal{C}$. Nonetheless, it is worth noting that if a modulus $m$ in $\mathcal{C}_0$ satisfies $m=p^\alpha r$ for some positive integer $\alpha$ such that $p\nmid r$, then the resultant modulus in $\mathcal{C}$ is $qp^{\alpha-1}r$.

[1] P. Erdős, On integers of the form $2^k+p$ and some related problems, Summa Brasil. math. 2 (1950), 113–123.

[2]
M. Filaseta, C. Finch, and M. Kozek, On powers associated with Sierpiński numbers, Riesel numbers and Polignac's conjecture, J. Number Theory 128 (2008), 1916–1940.

[3]
M. Filaseta, K. Ford, and S. Konyagin, On an irreducibility theorem of A. Schinzel associated with coverings of the integers, Illinois J. Math. 44 (2000), 633–643.

[4]
M. Filaseta, K. Ford, S. Konyagin, C. Pomerance, and G. Yu, Sieving by large integers and covering systems of congruences, J. Amer. Math. Soc. 20 (2007), 495–517.

[5]
M. Filaseta and J. Harrington, A polynomial investigation inspired by work of Schinzel and Sierpiński, Acta Arith. 155 (2012), 148–161.

[6]
M. Filaseta and W. Harvey, Covering subsets of the integers by congruences, Acta Arith. 182 (2018), 43–72.

[7]
M. Filaseta and J. Juillerat, Consecutive primes which are widely digitally delicate, preprint on arXiv (2021), https://arxiv.org/abs/2101.08898.

[8]  S. Guo and Z.W. Sun, On odd covering systems with distinct moduli, Adv. in Appl. Math. 35 (2005), 182–187.

[9]
J. Hammer, J. Harrington, and K. Marotta, Odd coverings of subsets of the integers, J. Comb. Number Theory 10 (2018), 71–90.

[10]
J. Harrington, Two questions concerning covering systems, Int. J. Number Theory 11 (2015), 1739–1750.

[11]
B. Hough, Solution of the minimum modulus problem for covering systems, Ann. of Math. 181 (2015), 361–382.

[12] R. D. Hough and P. P. Nielsen, Covering systems with restricted divisibility, Duke Math. J. 168 (2019), 3261–3295.

[13]
L. Jones and D. White, Sierpiński numbers in imaginary quadratic fields, Integers 12 (2012), 1265–1278.

[14]
P. Nielsen, A covering system whose smallest modulus is $40$, J. Number Theory 129 (2009), 640–666.

[15]
T. Owens, A covering system with minimum modulus $42$, Theses and Dissertations (2014), https://scholarsarchive.byu.edu/etd/4329.