View Single Post
Old 2008-11-11, 11:35   #2
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by jasonp View Post
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.
If r1 + k_i p1 = r2 + m_i p2 for some (k_i, m_i), then trivially

r2-r1 + m_i p2 = 0 mod p1, whence m_i = [r1-r2] * p2^-1 mod p1

What else are you looking for? It's just a linear congruence.
R.D. Silverman is offline   Reply With Quote