3
$\begingroup$

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

I'm not sure how to prove this. Could we possibly use the Chinese Remainder theorem? If so how?

$\endgroup$
  • $\begingroup$ Hint: if the numbers are consecutive, you can call them $ a+1, a+2, \ldots.$ Yes, CRT. E.g., $a+3 \equiv 0 \pmod{p_3}.$ $\endgroup$ – B. Goddard Mar 2 '18 at 18:33
1
$\begingroup$

We prove that the first prime can be arbitrary. The procedure is as follows: $$a_1=x+1\Rightarrow x\equiv -1\pmod {p_1}\\a_2=x+2\Rightarrow x\equiv -2\pmod {p_2}\\..................................\\...................................\\a_n=x+n\Rightarrow x\equiv -n\pmod {p_n}$$ (we can take optionally positive values, $p-1$ instead of $-1$ etc).

Take $$M=\prod_ïp_i=\text { and } A_j=\prod_{i\ne j}p_i$$ so we have $$M=p_jA_j\space \text {for all } j=1,2,\cdots, n$$ Calculate for each $j$ the inverse $z_j$ of $A_j$ modulo $p_j$ $$z_jA_j\equiv 1\pmod {p_j}$$ This way we have a solution $$x=z_1A_1(-1)+z_2A_a(-2)+\cdots+z_nA_n(-n)$$ Effective calculations could be somewhat arduous.

Example: $n=4\space\space p_1=5,p_2=7,p_3=11,p_4=13$

$$a_1=x+1\\x\equiv -1=4\pmod5\\x\equiv -2=5\pmod7\\x\equiv -3=8\pmod{11}\\x\equiv -4=9\pmod{13}\\$$ $$M=5\cdot7\cdot11\cdot13=5\cdot1001=7\cdot715=11\cdot455=13\cdot385\\1001\cdot1\equiv 1\pmod5\\715\cdot1\equiv 1\pmod7\\455\cdot3\equiv 1\pmod{11}\\385\cdot5\equiv 1\pmod{13}$$ Consequently a solution is $$x=1001\cdot4+715\cdot5+455\cdot3\cdot8+385\cdot5\cdot9=35824\\a_1=35825\\a_2=35826\\a_3=35827\\a_4=35828$$

$\endgroup$

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.