# Is there any known configuration of primes through $n$ which covers $n^2$?

Is there any known initial arrangement of prime residues (apologies in advance, I'm going to play fast and loose with the nomenclature) through some $$n$$ such that for every value in $$[n+1,n^2]$$, some value in $$[1,n]$$ can divide it? I feel confident the answer is no, but I don't think I've seen this explicitly asked before.

I know this certainly doesn't happen naturally, as established record gaps arising in $$\mathbb N$$ are far smaller than this. I'm referring to if you are allowed, informally speaking, to simply place prime numbers wherever you like up through $$n$$. For instance, you are free to choose to place $$2$$ at $$n=1$$, resulting in the coverage of all values $$\equiv 1 \pmod 2$$. You may even choose to place $$3$$s at $$n=2$$ and $$n=3$$, covering values $$\equiv \{0,2\} \pmod {3}$$. Given a successful configuration, after sieving out those values in $$[n+1,n^2]$$ which are composite, there would need to be nothing remaining, no prime left in that interval with that chosen residue system.

The only restriction that seems necessary is to prohibit establishing a congruence such that every value is trivially eliminated, e.g. removing both even and odd numbers. In other words, a given prime $$p$$ may only be used in $$p-1$$ different offsets.

What I've read on Jacobsthal's function suggests that carefully ordered sets of primes can have surprisingly long runs$$-$$I think there's a weak upper bound of something like $$n^2 \log^2 {n}$$? It looks like this paper from Hagedorn (2009) also gives a calculated value for a covering run of $$742$$ using the first 49 primes.

As I've said, I would expect that this is impossible, but I would also expect there not to be a proof of it yet. That said, I will be delighted if I turn out to be wrong on either account, so please let me know, along with any other pointers of interesting work along these lines should it exist. And if this is all basically still a big unknown, I will begrudgingly accept that as an answer too.

• Must the moduli (not the residues) be usual primes in $\Bbb{N}$? – Eric Towers Nov 30 '19 at 18:06
• @EricTowers If I understand your question, no. $5 \pmod 4$ should be perfectly fine, if that's what you're asking. If you're referring to the $5$ part, then I think yes, they must be prime; my guess is that otherwise it's straightforward to construct a tidy little covering set? – Trevor Nov 30 '19 at 18:12

Allow me to reframe your question.

Let $$n \geq 2$$ be an integer and for each $$k$$ in $$[2,n]$$, there is a set $$P_k$$ of residues modulo $$k$$. The elements of $$P_k$$ are called Trevor-primes. A number, $$m$$, in $$[n+1,n^2]$$ is a Trevor-composite if there is a $$k$$ and a $$p \in P_k$$ such that $$m \cong p \pmod{k}$$.

Question: For each choice of $$n$$, if for each $$k$$ the $$P_k$$ are strict subsets of complete residue systems modulo $$k$$, can the $$P_k$$ be chosen so that every $$m$$ in $$[n+1,n^2]$$ is a Trevor-composite?

If that is your setting and question, ...

Summary: no for $$n < 5$$; yes for $$n \geq 5$$.

The answer is no for $$n = 2$$ since only one residue class is a Trevor-prime in $$P_2$$ and we have to cover both of $$3$$ and $$4$$ with that one residue, which is impossible.

For $$n = 3$$, we may choose residues for $$P_2$$ and $$P_3$$, but we must leave at least one residue unchosen in each. By the Chinese remainder theorem, since $$2$$ and $$3$$ are relatively prime, the period of pairs of residues modulo $$2$$ and $$3$$ is six. The interval $$[n+1, n^2] = [4,9]$$ contains $$9 - 4 + 1 = 6$$ integers, a complete period. Consequently, no matter which residue we omit from $$P_2$$ and which from $$P_3$$, there is an element of $$[4,9]$$ with those residues, which is not a Trevor-composite. Therefore, there is no solution for $$n = 3$$.

The same proof applies when $$n = 4$$ because the least common multiple of $$2$$, $$3$$, and $$4$$ is $$12$$ and $$4^2 - 5 + 1 = 12$$. But this proof suggests a way forward once the Chinese remainder theorem period is longer than the interval we wish to fill with Trevor-composites.

For $$n \geq 5$$, $$L = \mathrm{lcm}(2, 3, \cdots, n) > n^2 - (n+1)+1$$. (Why? $$n$$ and $$n-1$$ are relatively prime, so their product, $$n(n-1) = n^2 - n$$, divides the lcm. $$n(n-1)$$ is also equal to $$n^2 - (n+1)+1$$, the number of members of $$[n+1,n^2]$$. The lcm is also divisible by $$n-2$$ when $$n$$ is odd or $$\frac{1}{2}(n-2)$$ when $$n$$ is even. When $$n \geq 5$$, this additional factor is greater than $$1$$.)

For each $$k$$ set $$P_k$$ to be the complete set of residues modulo $$k$$, omitting the residue $$n^2 + 1 \pmod{k}$$. By the Chinese remainder theorem we have arranged for one integer per period of length $$L$$ to fail to be a Trevor-composite. That integer is $$n^2 + 1 \pmod{L}$$. Since the smallest representative of that residue class is $$n^2 + 1$$, which is not in the inteval $$[n+1, n^2]$$, we have arranged for every member of $$[n+1, n^2]$$ to be a Trevor-composite.