# Given $0 < p < n$, prove there exists $n$ consecutive natural numbers such that each natural is divisible by at least $p$ distinct primes.

Given $0 < p < n$, prove there exists $n$ consecutive natural numbers such that each natural is divisible by at least $p$ distinct primes.

Is there a general proof method to prove this statement?

I brushed up my knowledge on the Chinese Remainder Theorem and Euclid's Theorem since they seem relevant, but I cannot find the necessary insight.

• This problem seems relevant, but I do not fully understand the given answer and cannot generalize it. Help appreciated. Oct 23, 2014 at 10:33
• André's nice idea was that you first select $n$ disjoint sets $S_i, i=0,1,\ldots,n-1$, of $p$ distinct primes. Then you form the $n$ products $m_i$ of primes in sets $S_i,i=0,1,\ldots,n-1$. Because the sets $S_i$ were disjoint, the products $m_i$ are pairwise coprime. Then he applied the Chinese Remainder Theorem to find a sequence of $n$ consecutive natural numbers such that $(i+1)$th number in the sequence is divisible by $m_i$, and consequently by at least $p$ distinct primes. Oct 23, 2014 at 10:39
• We don't need the restriction, it just makes things confusing. Given any $P$, any $N$, there is a sequence of $N$ consecutives each divisible by at least $P$ primes. This was done in the solution referred to. I don't really want to write down the proof, it would be a near duplicate. Oct 23, 2014 at 12:09

We can find by the Chinese remainder theorem a $x$ such that:
$x\equiv -1\pmod{p_1\cdot p_2\cdots p_n}$
$x\equiv -2\pmod{p_{n+1}\cdot p_{n+2}\cdots p_{2n}}$
$x\equiv -n\pmod{p_{(n-1)\cdot n+1}\cdots p_{n\cdot n}}$
You can see easily that $x+1,x+2, \ldots x+n$ have each one of them at least $n$ prime factors which means at least $p$ prime factors.