# Proof for Elementary Number Theory

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?

• 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}.$ – B. Goddard Mar 2 '18 at 18:33

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$$