By the chinese remainder theorem, simply take an $a \equiv -i \mod p_i$ for $i=0,1,...,m$ with some distinct primes $p_i \equiv 1 \mod m$ (existing by Dirichlet's theorem). To avoid the full Dirichlet theorem: Let $m=r_1 \cdot r_2 \cdot ... \cdot r_k$ be the prime factorisation of $m$. Take distinct primes $q_{i,j}$ such that $q_j \equiv 1 \mod r_j$ (the existence of these primes was shown in http://www.problem-solving.be/pen/viewtopic.php?t=176 ). Now it suffices to take each $p_i = q_{i,1} \cdot q_{i,2} \cdot... \cdot q_{i,k}$ to get the result again.

But even choosing primes $p_i \equiv 1 \mod m$ avoids the full Dirichlet theorem, since there exists an elementary proof for this, given by Rotkiewicz (using cyclotomic polynomials) for the case when the first term of the arithmetic progression is $1$.

That elementary proof goes back to Gauß. It is still easier to prove it for prime moduli only as it avoids a couple of more subtle arguments, but if anyone wants to take a look at it: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=722&t=393347 .