Reminder Numbers pattern/relationship finding Algorithm

Hello Coders,

I need a little help regarding this small problem.
Given two number a and b and two reminders rem1 and rem2. You need to find all number x which is satisfying following condition.

x%a = rem1 and x%b = rem2

e.g. a=11, b=14, rem1=0, rem2=2 then ans is x=44

I know one simple solution is via for loop but that is not good approach.
Actually I need a formula or some pattern which will give me answer efficiently.

If a and b are coprime, then you can use chinese remainder theorem

1 Like

Link to similar question in stackoverflow.

link text

clearly
(x-rem1) is divisible by a
also (x-rem2) is divisible by b

now this both are arthematic progressions

find their common terms only is sol.

Even if a and b are not co prime we can apply CRT on their prime factors, like if we have to find X congruent to p mod a and X congruent to q mod b, and solutions to X, simply express the first one as X congruent to p mod all_prime_factors(a) and as they are coprime with b definitely and each other, apply CRT. This will work if we are guaranteed such X exists(otherwise just check for contradictions and say it is impossible). As we have only O(\log a) prime factors, this is still fast.

1 Like

Yes, the idea expressed by @nibnalin is what is actually done. I just gave a hint towards the answers. For code, you may look at https://github.com/BidhanRoy/Algorithm-Code-Library/blob/master/Mathematics/Chinese%20Remainder%20Theorem.cpp