View Single Post
Old 2008-11-11, 02:38   #1
Tribal Bullet
jasonp's Avatar
Oct 2004

2·3·19·31 Posts
Default Compositions of arithmetic progressions

So this has now come up several times in the course of building msieve code, and it's high time I tried to understand how to think about it.

Suppose you have two arithmetic progressions, r1 + k1 * p1 and r2 + k2 * p2. If p1 and p2 are coprime, how does one go about constructing a third arithmetic progression P = r3 + k3 * p1 whose members all lie on values of the p2 progression? Put another way, k3 is a multiple of p2, so that P maps the first progression onto the lattice formed by the second.

I know that when r2 is zero, then r3 is r1 * modinverse(p2,p1) mod p1, where modinverse(x,y) is the modular inverse of x modulo y. What I don't understand is how to generalize this to the case of arbitrary r2.

Apologies if this is too basic. The case when p1 and p2 share factors is also of interest, though less so.
jasonp is offline   Reply With Quote