1
$\begingroup$

Prove that for any positive integer $n$, there exist $n$ consecutive positive integers $a_1, a_2,...,a_n$ such that $p_i |a_i $ for each $i$, where $p_i$ denotes the $i$th prime?

Having a lot of trouble with this problem, I tried searching this question up but only got problems similar to it and it still didn't quite help. We are currently covering a section on The Chinese Remainder Theorem. Our teacher showed us two ways of utilizing this theorem, one via back-substitution and one via the classical approach. Looking through my notes I don't see anything resembling this problem, any help is really appreciated.

$\endgroup$
1
$\begingroup$

Using the Chinese Remainder Theorem:

Consider solutions to $$ \begin{align} x &\equiv 0 \pmod 2 \\ x+1 &\equiv 0 \pmod 3 \\ x+2 &\equiv 0 \pmod 5 \\ \cdots \\ x+n &\equiv 0 \pmod {p_{n+1}}. \end{align}$$

Then the Chinese Remainder Theorem guarantees your solution, which is exactly a collection of $(n+1)$ consecutive integers $x, x + 1, x + 2, \ldots, x+n$ with the desired divisibility conditions.

$\endgroup$
  • $\begingroup$ I'm still not quite seeing what you mean, how did you get those solutions, I'm not sure how it guarantees the given solution? $\endgroup$ – Nick Powers Mar 5 '16 at 19:51
  • $\begingroup$ The moduli are relatively prime, so the Chinese remainder theorem guarantees that there is an $x$ that is a simultaneous solution. Then $x, x+1, x+2, \ldots$ is your collection of consecutive integers. $\endgroup$ – davidlowryduda Mar 5 '16 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.