View Single Post
Old 2011-08-20, 09:01   #8
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

1,429 Posts

The complete solution is known from Number Theory, see:

To find the same terms of two arithmetic progressions of:
(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==r2-r1 mod n2
This is solvable if and only if gcd(n1,n2)|(r2-r1) and in this case divide by gcd(n1,n2), you get:

x*n1/gcd(n1,n2)==(r2-r1)/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 2011-08-20 at 09:03
R. Gerbicz is offline   Reply With Quote