退出

When does a non-empty CRT residue set meet a short interval?

数论 Math StackExchange -4 票 0 回答 30 浏览 提问者: Kant 2026-08-18 13:51
number-theory elementary-number-theory modular-arithmetic chinese-remainder-theorem sieve-theory

问题内容

Let $m_1,\ldots,m_s$ be pairwise coprime positive integers, and let

$$ M=\prod_{i=1}^s m_i. $$

For each $i$, let $A_i$ be a non-empty proper subset of residue classes modulo $m_i$. Define the CRT-allowed residue set $S \pmod M$ by

$$ S=\{x \pmod M : x \pmod {m_i} \in A_i \text{ for every } i\}. $$

By the Chinese remainder theorem,

$$ |S|=\prod_{i=1}^s |A_i|, $$

so $S$ is non-empty as a subset of residue classes modulo $M$.

My question is about the local version.

Let

$$ I=[a,a+L-1] $$

be a specific interval of integers, possibly much shorter than $M$.

What additional hypotheses are needed to guarantee that

$$ I\cap S\neq \varnothing? $$

Equivalently, when can one pass from the full-period CRT fact

$$ S\neq \varnothing \pmod M $$

to the local conclusion that a particular interval $I$ contains an integer whose residues lie in all the allowed sets $A_i$?

One obvious sufficient condition is in terms of the largest gap between consecutive representatives of $S$ modulo $M$. If $G(S)$ denotes this largest gap, then every interval of length greater than $G(S)$ meets $S$.

My questions are:

  1. Is this the standard way to formulate the problem?
  2. Is there standard terminology for $G(S)$ in this general CRT setting?
  3. Are there known general bounds for $G(S)$ in terms of the moduli $m_i$ and the sizes or structure of the sets $A_i$?
  4. Is this considered a Jacobsthal-type problem, a covering congruence problem, or something else?

Any references or corrections to the formulation would be appreciated.

回答 (0)

暂无回答记录。