If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called [covering systems][1] and the linked article looks good. 

As you point out, you can use any set of primes, say primes of the form $10^k+3$ (If there are infinitely many, maybe safer to use $10+1, 10^2+1, 10^3+9, 10^4+7, 10^5+3, 10^6+3, 10^7+19, 10^8+7 \cdots$ smallest primes with each number of digits). So a better question might be: if you use all the primes, how sparse a set of residues can you use?




  [1]: http://en.wikipedia.org/wiki/Covering_system