I might as well make this thread the dumping ground for all the problems I have with arithmetic progressions. Here's the latest, a consequence of an insidious bug in msieve that I'm trying to fix:
Suppose you have a bunch of different arithmetic progressions
R0 + i * p^k
where p is prime and p^k is small (say less than 1000). There are lots of different R0, up to p^k of them. I need to 'map' each of these progressions onto a lattice of size L, i.e. to find another arithmetic progression
R0' + j * p^k
such that every value of that second progression lies on a lattice A + m * L.
When L and p^k are coprime this is easy, and was addressed by Bob's post above. In fact with many R0 you can find R0' via a single table lookup: maintain an array of size p^k and put j at location (A+j*L) mod p^k for each j in turn, so that R0' = table[R0].
What I evidently don't understand is what to do when p divides L one or more times. I originally assumed that the table lookup method described above still works, except that
 R0' may not exist depending on the precise value of A and L
 the new progression would have a step value of p^k / gcd(L, p^k) and not p^k
but I've noticed numerical examples where that's not true. Rather than trying to fit a heuristic to data, I was wondering how to solve this (embarrassingly easy sounding) problem analytically.
