4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ This problem seems relevant, but I do not fully understand the given answer and cannot generalize it. Help appreciated. $\endgroup$
    – nande2121
    Oct 23, 2014 at 10:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Oct 23, 2014 at 10:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Oct 23, 2014 at 12:09

1 Answer 1

Reset to default
2
$\begingroup$

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}}$
and the primes are chosen to be all different.
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.

$\endgroup$
2
  • $\begingroup$ What allows assuming "and the primes are chosen to be all different"? $\endgroup$
    – nande2121
    Oct 23, 2014 at 21:11
  • $\begingroup$ @nande2121 the Chinese remainder theorem. It is says exactly this. $\endgroup$
    – Konstantinos Gaitanas
    Oct 24, 2014 at 7:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .