Let there exist a prime $p< M$ such that $p$ does not divide $d=a_2-a_1$. $a_i \equiv a_1+(i-1)d \mod p$ Also as $n \ge M > p$, by PHP we get a complete residue system of $i$ in modulo $p$. So there exists $N \le n$ such that $N \equiv (1-a_1x) \mod p$, where $x$ is inverse of $d$ in modulo $p$. Simply it follows that $a_N \equiv 0 \mod p$ $\implies a_N = p$ But $a_N > a_1 > M > p$ which is a contradiction. So the desired statement follows.