The complete solution is known from Number Theory, see:
To find the same terms of two arithmetic progressions of:
r1+x*n1
r2+y*n2
(In your case n1=p^k, n2=L)
Suppose that:
r1+x*n1=r2+y*n2, from this
r1+x*n1==r2 mod n2
x*n1==r2r1 mod n2
This is solvable if and only if gcd(n1,n2)(r2r1) and in this case divide by gcd(n1,n2), you get:
x*n1/gcd(n1,n2)==(r2r1)/gcd(n1,n2) mod n2/gcd(n1,n2)
and here gcd(n1/gcd(n1,n2),n2/gcd(n1,n2))=1 so this system is solvable.
And there is exaclty one solution mod n2/gcd(n1,n2)
Last fiddled with by R. Gerbicz on 20110820 at 09:03
