Start with $\{1\}$. Now go from $\{a_1,\cdots a_n\}$ to \[ \{ab^2-1,ab^2+ba_1,\cdots ab^2+ba_n\} \] for $b=a_1a_2\cdots a_n$ and $ab^2\equiv 1 \pmod{(ba_1+1)(ba_2+1)\cdots (ba_n+1)}$, $a\ge 2$. First, to show that such an $a$ exists, we must prove that $ba_i+1, ba_j+1$ are relatively prime, and that $b^2,ba_i+1$ are relatively prime. If this is true, we can take the inverse of $b^2\pmod{ba_i+1}$ for each $i$ and apply CRT (making $a\ge 2$ by making it arbitrarily large of course). Suppose we had $p\mid ba_i+1,p\mid ba_j+1$. Then we would have $p\mid b(a_i-a_j)\mid ba_i\mid b^2$, so $p\mid b$ contradicts $p\mid ba_i+1$. Suppose we had $p\mid b^2, p\mid ba_i+1$. Then we get a contradiction similarly. So we can indeed find such an $a$. Now we consider all pairs of positive integers in the new set, and show that they satisfy the given condition. Case 1: $x=ab^2+ba_i$, $y=ab^2+ba_j$. Then $x-y=b(a_i-a_j)\mid ba_i\mid b^2$, so \[ x-y\mid ab^2+ba_k\Leftrightarrow x-y\mid ba_k\Leftrightarrow b(a_i-a_j)\mid ba_k\Leftrightarrow a_i-a_j\mid a_k \] which is true iff $k=i,j$ by the inductive hypothesis. Case 2: $x=ab^2+ba_i,y=ab^2-1$. Then $x-y=ba_i+1$. So by our construction of $a$, $x-y\mid y$ and thus $x-y\mid x$. Suppose for sake of contradiction we had $x-y\mid z$ for $z$ in the set distinct from $x,y$. Then $x-y\mid z-x$, or equivalently \[ ba_i+1\mid (ab^2+ba_i)-(ab^2+ba_j)=b(a_i-a_j)\mid b^2 \] but $\gcd(b^2,ba_i+1)=1$ and $ba_i+1\ge 2$, so this is a contradiction.

Here was the solution I found: The idea is to look for a sequence $d_1, \dots, d_{n-1}$ of ``differences'' such that the following two conditions hold. Let $s_i = d_1 + \dots + d_{i-1}$, and $t_{i,j} = d_i + \dots + d_{j-1}$ for $i \le j$. No two of the $t_{i,j}$ divide each other. There exists an integer $a$ satisfying the CRT equivalences \[ a \equiv -s_i \pmod{t_{i,j}} \quad \forall i \le j \] Then the sequence $a+s_1$, $a+s_2$, \dots, $a+s_n$ will work. For example, when $n=3$ we can take $(d_1,d_2)=(2,3)$ giving \[ 10 \overbrace{\underbrace{\qquad}_2 12 \underbrace{\qquad}_3}^5 15 \]because the only conditions we need satisfy are \begin{align*} a &\equiv 0 \pmod 2 \\ a &\equiv 0 \pmod 5 \\ a &\equiv -2 \pmod 3. \end{align*}But with this setup we can just construct the $d_i$ inductively. To go from $n$ to $n+1$, take a $d_1, \dots, d_{n-1}$ and let $p$ be a prime not dividing any of the $d_i$. Moreover, let $M$ be a multiple of $\prod_{i \le j} t_{i,j}$ coprime to $p$. Then we claim that $d_1M, d_2M, \dots, d_{n-1}M, p$ is such a difference sequence. For example, the previous example extends as follows with $M = 300$ and $p=7$. \[ a \overbrace{\underbrace{\qquad}_{600} b \overbrace{\underbrace{\qquad}_{900} c \underbrace{\qquad}_{7}}^{907}}^{1507} d \]The new numbers $p$, $p+Mt_{n-1,n}$, $p+Mt_{n-2,n}$, \dots\ are all relatively prime to everything else. Hence (i) still holds. To see that (ii) still holds, just note that we can still get a family of solutions for the first $n$ terms, and then the last $(n+1)$st term can be made to work by Chinese Remainder Theorem since all the new $p+Mt_{n-2,n}$ are coprime to everything.

My solution set is a lot like pi37's solution set, but I'll write it down anyway with some motivation. Note that trivial sets exist for $n = 2$. We shall construct the subset for each $n$ by induction on $n$. Suppose that ${ a_1, a_2, \cdots a_n } $ is one such subset. The set to be created is called $B$ and its elements $b_i \forall i \in [1, n+1]$. Then, whenever $a_i-a_j|a_k \Longleftrightarrow k$ must be either $i$ or $j$. This property shall continue to exist (almost) if we take $b_i$ to be a linear function of $a_i$. Let $b_i = ba_i+c \forall i \in [1,n]$. If $b_i-b_j|b_k$ for some $i, j, k \in [1,n]$, then $b(a_i-a_j)|ba_k+c$, implying $b|c$. Let $c = bc'$. Then, $b_i = b(a_i+c')$ and therefore, the last relation becomes $a_i-a_j|a_k+c' \implies a_i-a_j|c'$. This motivates us to choose $c'$ to be a multiple of $a_1a_2 \cdots a_n = P$, say $c' = MP$. Now we need to suitably choose $b_{n+1}$ so that $b_{n+1}-b_i|b_k \Longleftrightarrow k = n+1$ or $i$. Now, we would like to have $b_{n+1}$ such that the we can easily choose $M$ to satisfy $b_{n+1}-b_i|b_{n+1}$. To serve this purpose, we eliminate $bMP$ from the LHS of the divisibility criterion, i.e. we take $b_{n+1} = bMP+d$, where d is some constant. This gives $ba_i-d|bMP+d$. Now, to apply CRT, we need $ba_i-d$'s coprime. Suppose there is some prime $p$ such that $p|ba_i-d$ and $ba_j-d$. Then, $p|b(a_i-a_j)|ba_i \implies p|d$. We shall make this impossible by choosing $d = 1$. ($d = -1$ also works). We need to have $b$ such that $\text{gcd}(bP, ba_i-1) = 1$. Choosing $b = P$ immediately does it. Then, we get $b_{n+1}-b(a_i+MP) = ba_i-1|bMP+1$, i.e. $M \equiv -(bP)^{-1} \pmod{ba_i-1}$. Suppose now that $b_{n+1} = ba_i-1|b_j = b(a_j+MP)$. Then, $ba_i-1|ba_j-1 \implies ba_i-1|b(a_j-a_i)$. For $i \neq j$, $ba_i-1|ba_i$, contradicting $(ba_i-1, ba_i) = 1$.

We choose a prime $t >\prod a_i$. Basically choosing a $t$ such that $ma_i-t$ s are coprime and then solving $x \equiv -t (mod ma_i-t)$ gives us the condition $b_n-b_i|b_n$ for all $i$.(Here $b_i=ma_i+x$)Now for proving that $b_i-b_j$ doe not divide $b_n$ for $i,j$ within $1$ to $n-1$,notice we have not used any restriction on $m$.So time is to put some.Take $m= \prod a_i$.Let some prime $q|m$ and $q|ma_i-t$.Then $q|t$.But as $t$ is prime , $t>m$and $q|m$,this contradicts.Thus $(m,ma_i-t)=1$So in the previous list of congruences to solve,just add $x \equiv 0 (mod m)$. Now let $b_i-b_j|b_n$.Hence $m(a_i-a_j)|b_n=x+t$,But $m|x$ and so $m|t$,which contradicts.Hence we get the sequence $x+ma_1,x+ma_2,...x+ma_n,x+t$ which satisfies everything. Had to write in a hurry and also my proof is quite non-rigorous,so point out any flaw.

I had a pretty messy solution, but I felt like it was very motivated (and it got 7/7 on the test). The first thing I noticed was that the problem looked oddly similar to USAMO 1998 #5, which I luckily remembered the solution to. This problem just begs for an inductive approach, and based on the USAMO problem, I was looking at linear transforms. Lets say we have a working sequence $ a_1, a_2, a_3, \dots, a_n. $ We want to add an $ x $ to this sequence so that all the divisibility conditions still hold. We need to modify the original sequence to do that. In the spirit of the USAMO problem, by letting $ Z = lcm(a_1, a_2, \dots, a_n) $, we know that any sequence of the form $ a_1 + sZ, a_2 + sZ, \dots, a_n + sZ $ works as well for any $ s \in \mathbb{N}. $ We also know that the sequence $ ra_1, ra_2, \dots, ra_n $ works for any $ r \in \mathbb{N}. $ Combining these two ideas we have that any sequence of the form $ ra_1 + rsZ, ra_2 + rsZ, \dots, ra_n + rsZ $ works. This gives us a lot of freedom! Now, let's say we append an $ x + rsZ $ this sequence. We need exactly three things to be true for the new sequence to work: $ 1) $ $ x - ra_i \vert ra_i + rsZ $ for every $ i \in \{1, 2, \dots, n\} $ $ 2) $ $ x - ra_i \nmid ra_j + rsZ $ for every distinct $ i, j \in \{1, 2, \dots, n\} $ $ 3) $ $ r(a_j - a_i) \nmid x + rsZ $ for every distinct $ i, j \in \{1, 2, \dots, n\} $ We can handle Condition $ 3 $ easily by specifying that $ r \nmid x. $ Now assume that Condition $ 1 $ holds. For Condition $ 2 $ to fail, there would have to exist distinct $ i $ and $ j $ such that $ x - ra_i \vert ra_j + rsZ. $ But since we assumed Conditon $ 1 $ to hold, we also know that $ x - ra_i \vert ra_i + rsZ. $ Therefore $ x - ra_i \vert r(a_i - a_j). $ This is easily prevented by making $ x $ sufficiently larger than $ r. $ So, we only REALLY care about Condition $ 1. $ Now, fix a sufficiently large $ r $ such that there exists infinitely many $ x $ such that the $ x - ra_i $ values are pairwise coprime (such an $ r $ clearly exists by CRT). Choose an $ x $ sufficiently larger than $ r $ that is not divisible by $ r $ that makes each of the $ x - ra_i $ values pairwise coprime as well as all coprime to $ Z. $ Now by CRT there is a solution for $ s $ that allows Condition $ 1 $ to hold, so we can find an $ x $ that satisfies all three conditions and so we are done by induction (the base cases are trivial).

Assume we have found numbers $a_1, ..., a_n$ that work for $n$, we want to find a sequence $b_1, ..., b_{n+1}$ that works for $n+1$. Notice that applying a "linear transformation" (not really) to the original sequence preserves the property. That is, if we replace $a_i$ by $ka_i+s$ (where $s$ is a multiple of all the $ka_i$), nothing changes. The sequence still works. Let's apply this transformation and we will try to find a good $b_{n+1}$. Given that $b_1, ..., b_n$ is a sequence that works, we want $x=b_{n+1}$ to work. We need $b_i-b_j | x$ to be false if $i, j < n+1$. Notice that $k | b_i-b_j$, so if $k$ doesn't divide $x$, this is enough. Now let's write $x=y+s$ where $y$ isn't a multiple of $k$. Simply choose $y$ coprime to $k \left( \displaystyle\prod_{i<j} a_j-a_i \right) \left( \displaystyle\prod_{i=1}^n a_i \right)$. We need $y - ka_i | y+s$ for $i < n+1$. Notice that if we have that $y-ka_i$ are all coprime and greater than 1, then by Chinese theorem we can choose such an $s$. Since wlog $y-ka_i$ is coprime to $ka_i$, one can also make this $s$ a multiple of all the $ka_i$ by Chinese theorem. This would also guarantee that $y-ka_i$ doesn't divide $ka_j+s$ for $i \neq j$ since that would imply $y-ka_i | y-ka_j$. So we must prove that the $y-ka_i$ are all coprime and greater than 1. If we had $d | y-ka_1$ and $d | y-ka_2$ then we have $d | k(a_1-a_2)$. But if $(d,k) \neq 1$ then $(d,k) | y-ka_1$ impossible since $(y,k)=1$. Therefore $d | a_1-a_2 | a_1$ and therefore $d | y$. Impossible.

We use induction Let we find $N$numbers such that they have this situation So we name them $a_1,a_2,...,a_n$ Let $T=a_1a_2a_3...a_n$ We can say that the numbers $T,T+a_1,T+a_2,...,T+a_n$ have this situation so we made $n+1$ numbers so we are done

hayoola wrote: We use induction Let we find $N$numbers such that they have this situation So we name them $a_1,a_2,...,a_n$ Let $T=a_1a_2a_3...a_n$ We can say that the numbers $T,T+a_1,T+a_2,...,T+a_n$ have this situation so we made $n+1$ numbers so we are done Wrong! Notice that for any $i,j$ we have $a_i-a_j=(T+a_i)-(T+a_j)$,and $a_i-a_j|gcd(T,T+a_i,T+a_j)$

Induct on $n=1$ the base case being say $(a_1,a_2)=(2,3)$.Now we construct $\{b_i\}_{i=1}^{n+1}$ as $b_i=2^{M}-2^{a_i}$ $\forall i\leq n$ and $b_{n+1}=2^{M}-1$ where $M=\prod_{i=1}^{n}a_i$ and $\{a_i\}_{i=1}^{n}$ being the sequence satisfying the conditions for $n$. $b_i-b_j\mid b_i$ as $a_i-a_j\mid M-a_i$.If $b_i-b_j\mid b_z$ where $i,j\not =n+1$ and for the sake of argument let $z\not= i,j$ $\implies$ $2\mid b_z$ as inductively all the numbers are different.Note that this discards $z=n+1$ as $2\not|b_{n+1}$.Now :$2^{a_i-a_j}-1\mid 2^{M-a_z}-1$$\implies$ $a_i-a_j\mid M-a_z$,$z$ not being $i,j$ $\implies$ $\tfrac{M}{a_z}$ is divisible by $a_i-a_j$ so in order for the divisibility to holds one needs that $a_i-a_j\mid a_z$ a contradiction with the inductive assumption. $b_i-b_{n+1}\mid b_{n+1}$ as $a_i\mid M$.Suppose that $b_{n+1}-b_i\mid b_z$ $\implies$ $2^{a_i}-1\mid 2^{M-a_z}-1$ as $a_i\mid \tfrac{M}{a_z}$ $\implies$ $a_i\mid a_z$.Let's show by induction that this cant ever happen the base case being obvious.Suppose the sequence is generated out of $c_1,c_2,...c_{n-1}$ ,$a_i\mid a_z$ $\implies$ $M'-c_i\mid M'-c_z$ $\implies$ $c_i\mid c_z$ ,as $c_i\mid \frac{M'}{c_z}$, a contradiction by inductive hypothesis.$\blacksquare$

Stranger8 wrote: hayoola wrote: We use induction Let we find $N$numbers such that they have this situation So we name them $a_1,a_2,...,a_n$ Let $T=a_1a_2a_3...a_n$ We can say that the numbers $T,T+a_1,T+a_2,...,T+a_n$ have this situation so we made $n+1$ numbers so we are done Wrong! Notice that for any $i,j$ we have $a_i-a_j=(T+a_i)-(T+a_j)$,and $a_i-a_j|gcd(T,T+a_i,T+a_j)$ Well... hayoola is right $(T+a_i)-(T+a_j)=a_i-a_j|a_i|T+a_i$ and $(T+a_i)-(T+a_j)=a_i-a_j|a_j|T+a_j$ I can't understand why hayoola's solution is wrong

for63434 wrote: Well... hayoola is right $(T+a_i)-(T+a_j)=a_i-a_j|a_i|T+a_i$ and $(T+a_i)-(T+a_j)=a_i-a_j|a_j|T+a_j$ I can't understand why hayoola's solution is wrong It's more subtle than that ,what differs this problem from the classic one, is that $a-b$ divides $a,b$ and only them ,whereas in hayoola's solution we have three numbers $T,T+a_i,T+a_j$.

for63434 wrote: Stranger8 wrote: hayoola wrote: We use induction Let we find $N$numbers such that they have this situation So we name them $a_1,a_2,...,a_n$ Let $T=a_1a_2a_3...a_n$ We can say that the numbers $T,T+a_1,T+a_2,...,T+a_n$ have this situation so we made $n+1$ numbers so we are done Wrong! Notice that for any $i,j$ we have $a_i-a_j=(T+a_i)-(T+a_j)$,and $a_i-a_j|gcd(T,T+a_i,T+a_j)$ Well... hayoola is right $(T+a_i)-(T+a_j)=a_i-a_j|a_i|T+a_i$ and $(T+a_i)-(T+a_j)=a_i-a_j|a_j|T+a_j$ I can't understand why hayoola's solution is wrong $a_{i}-a_{j}$not only divides$T+a_{I}$,$T+a_{j}$but also $T$ which is not required in this problem! Be careful

Oh.. i get it Thanks for pointing it out !

v_Enhance wrote: Prove that for every $n\in \mathbb N$, there exists a set $S$ of $n$ positive integers such that for any two distinct $a,b\in S$, $a-b$ divides $a$ and $b$ but none of the other elements of $S$. Proposed by Iurie Boreico This is a really amazing problem!

I think this solution is wrong. p is nor a multiple of ak-p

The argument is by induction on $n$. Of course, the result is meaningless for $n=1$. Let the elements of the set $S$ be ordered as \[a,a+d_1,a+d_1+d_2,\dots,a+d_1+\cdots+d_{n-1}.\]Start by setting $d_1=2$ so we can win by requiring $2\mid a$. At each step of the induction, let $a$ be a residue modulo \[M=\prod_{i\ne j}(d_j+d_{j-1}+\cdots+d_i)\]so that the condition will be satisfied. Then clearly replace each $d_i$ with $Md_i$. Let $p$ be a prime greater than $M$. Note that $M[d_i+d_{i+1}+\cdots + d_{n-1}]+p$ is relatively prime to any $M[d_i+d_{i+1}+\cdots+d_j]$ and thus to any $M[d_i+d_{i+1}+\cdots+d_{n-1}]+p$. Hence we can require $a\equiv -M[d_1+d_2+\cdots+d_{i-1}]\pmod{M[d_i+d_{i+1}+\cdots+d_{n-1}]+p}$ for all $i$ by CRT, which finishes.

We claim that for any $n,$ there exists a sequence of positive integers $d_1,d_2, \dots ,d_n$ such that there exists an integer $a_n$ where $\{a_n+d_1, a_n+d_1+d_2, \dots , a_n+d_1+d_2 + \dots +d_n \}$ works. It suffices to have for any integers $1\le i < j \le n,$ $a_n \equiv -(d_1+ \dots + d_{i}) \pmod{d_{i+1} +\dots +d_{j}}$ and $a_n \not\equiv -(d_1 + \dots + d_{k}) \pmod{d_{i+1}+d_{i+2} +\dots +d_{j}}$ for any index $k \ne i, j.$ We induct on $n,$ base case of $1$ being trivial. Suppose we have a valid sequence $d_1, d_2, \dots d_n.$ Let $P = d_1d_2 \dots d_n.$ Let $L$ be the lcm of $P$ and all the $d_i+d_{i+1}+\cdots+d_j.$ Take a prime $p > L.$ We claim $Pd_1,Pd_2, \dots Pd_n, p$ works. For any integers $1 \le i < j \le n,$ let $a_{n+1} \equiv Pa_n \pmod{P(d_{i+1}+\dots +d_{j})}$ implying $$a_{n+1} \equiv -P(d_1 + \dots + d_{i}) \pmod{P(d_{i+1}+\dots +d_{j})}$$and $$a_{n+1} \not\equiv -P(d_1+ \dots + d_{k}) \pmod{P(d_{i+1}+\dots +d_{j})}$$for any index $k \le n$ that is $\ne i, j.$ Furthermore $$a_{n+1} \not\equiv -P(d_1+d_2 + \dots + d_{n})-p \pmod{P(d_{i+1} +\dots +d_{j})}$$since $p \nmid L.$ Also let $$a_{n+1} \equiv -P(d_1+ \dots + d_{i}) \pmod{P(d_{i+1} +\dots +d_{n})+p}$$for all $1 \le i \le n$ implying $$a_{n+1} \not\equiv -P(d_1 + \dots + d_{k}) \pmod{P(d_{i+1} +\dots +d_{n})+p}$$for all $1 \le k \le n$ not equal to $i;$ otherwise $P(d_{i+1}+ \dots + d_{k})$ or $P(d_{k+1}+ \dots + d_{i})$ is $\equiv 0 \pmod{P(d_{i+1} +\dots +d_{n})+p}.$ This is impossible if $p > L.$ Since all the $P(d_{i+1}+ \dots + d_n)+ p$ are relatively prime to each other and $L$ there exists a valid $a_{n+1}$ by CRT.

Posting for storage My thought process is as follows: 1. If S is a working set, then for some integer $k$, $S+k$ works (this means add $k$ to everything), so it makes sense to focus on the differences. Rewrite the set as $K-x_1, \cdots, K-x_n$ 2. The condition that only $a,b$ divide $a-b$ is kind of awkward. To fix this, assign a prime $p_{i,j}>n^{n^{100n}}$ to $(i,j)$ such that $p_{i,j}| x_k-x_l$ ($k\ne l$) iff $\{i,j\}=\{k,l\}$ 3. Eliminate $K$. If $x_1,\cdots,x_n$ are fixed, we'd be solving for a system of congruences of the form$$K\equiv x_i (\bmod\; lcm(|x_i-x_{i+1}|, \cdots, |x_i-x_n|))$$Write $L_i=lcm(|x_i-x_{i+1}|, \cdots, |x_i-x_n|)$ for laziness. It is left as an exercise for you to show that we can find $K$ if and only if $\nu_p(x_i-x_j)\ge \min\{ \nu_p(L_i), \nu_p(L_j)\}$ Now we construct $x_i$ in the order $x_n, x_{n-1}, \cdots$. We will make $\nu_p(x_k)=n-k$ for all $p<n$, which means we will only have to deal with large primes, for which we have enough residues to walk around. Thus we only focus on primes $>n$ (call these primes large). In fact we can make $\min\{ \nu_p(L_i), \nu_p(L_j)\}$ equal to 0 for all large primes. Construct $x_n, x_{n-1}$ arbitrarily as long as $p_{n-1,n}$ divides their difference. Let $T$ be a set of large primes. Put all large primes (including $p_{ij}$'s) that divide $x_n-x_{n-1}$ in $ T$. When we have $x_{m+1},\cdots, x_n$ and want to construct $x_m$, $T$ will contain all large prime factors of $\prod_{m<i<j<n} |x_i-x_j|$. We first let $x_m$ satisfy $\nu_p$ restrictions for primes $\le n$ and $p_{m,k}$ where $k>m$. It must also be not equivalent to any of the $x_k$'s ($k\in (m,n]$) mod any prime in $T$, which is possible since these primes are large. Thus by CRT we can construct $x_m$. Now insert all large prime factors of $|x_m-x_k|$ into $T$ where $k>m$. This method guarantees $x_i-x_j$'s share no large prime factors, so it is fine.

Outline of solution. We show this by induction on $n$. We choose a sequence $z+a_1,z+a_2,...,z+a_n$, and then we construct a proper $z$. First, we prove there exists a set of numbers such that all the differences are coprime to each other except by primes less than $n$ and such that all the exponents of those small primes are different for each $a_i$. This is actually trivial by induction and CRT: Suppose we have chosen and we want to add $A$. Now, make $A=(\prod p_i)^T.k$, for some big $T$ and small $p_i$. Now, we choose $k$ by CRT in such a way that $A-a_i$ is not divisible by any prime that divides the other differences (there is a finite quantity of those) which is trivial by CRT. We want $$a_i-a_j | z+a_i$$. Now, to finish, just choose $z=(\prod p_i)^L.j$, for some big $L$, where $p_i$ are the small primes and some proper $L$. Notice that the exponent of the small primes of the difference is the minimum between $a_i$'s and hence divisible by those primes on the difference and $z$ has big exponent, so $z+a_i$ is actually divisible by the exponent of the small primes of those differences, and is not divisible by any other difference by our construction below, because if it were, then $a_i-a_j | (z+a_k)-(z-a_i)$ and thus $a_i-a_j | a_k-a_i$, which is impossible by our construction. Now, choose $L$ by CRT on the big primes of $a_i-a_j$ and their exponents (they are all different by construction).

We parametrize $S$ instead in terms of $a_1 = a$ and $d_i = d_{i+1} - d_i$ for $1 \leq i \leq n-1$, as usual. We may construct a valid set $S$ with $n$ elements inductively as follows: pick an integer $N$ such that $d_i + d_{i+1} + \cdots + d_j$ divides $N$ for all $i \leq j$ and a prime $p$ relatively prime to all of the $d_i$. Then it suffices for $a_1$ to satisfy \begin{align*} p &\mid a_1 +M(d_1+d_2+\cdots+d_{n-1}) \\ p+Md_{n-1} &\mid a_1 + M(d_1+d_2+\cdots+d_{n-2}) \\ p+M(d_{n-1}+d_{n-2}) &\mid a_1+M(d_1+d_2+\cdots+d_{n-3}) \\ \vdots &\mid \vdots \end{align*}where all of the divisors are pairwise relatively prime by selection of $p$ and $M$. It follows we may select suitable $a_1$ by Chinese Remainder theorem.