Using Chinese Remainder Theorem
A bag has certain number of pens. If you take out 3 pens at a time, 2 pens are left, if you take 4 pens, 1 pen is left and if you take 5 pens at a time, 3 pens are left in the bag. What is the smallest number of pens in the bag?
Problems of this kind can be solved by using the Chinese remainder theorem. In order to understand the Chinese remainder theorem its helpful to have a basic understanding of modular arithmetic.
In modular arithmetic,
For a positive integer n, two integers a and b are said to be congruent modulo n, and written as
a ≡ b (mod n)
if their difference a − b is an integer multiple of n (or n divides a − b).
You can check this link for further details on modular arithmetic.
In this video we have explained the Chinese Remainder theorem with an example and hopefully you will know how to use the Chinese Remainder theorem to solve problems of the kind mentioned above.