Thread: mathematics gcd problems

hi,
plz help me solve following.thanks
Q3) Find two numbers between 100 and 150 that have an HCF of 24.?
Ans: 120 and 144
Q4) find the least number between 200 and 500 which leaves a remainder of 3 in each case when divided by 8, 10, 12 and 30?
Ans: 243
any help would be highly appreciated.

Originally Posted by gufog1

Q3) Find two numbers between 100 and 150 that have an HCF of 24.?
Ans: 120 and 144

There are not so many multiples of 24 between 100 and 150...

Originally Posted by gufog1

Q4) find the least number between 200 and 500 which leaves a remainder of 3 in each case when divided by 8, 10, 12 and 30?
Ans: 243

When the divisors are pairwise coprime, the solution to such problem exists and is found using the Chinese remainder theorem. Applying it, however, involves Euclid's algorithm and requires some work (calculating an inverse modulo can be simplified a little using an iterative procedure described in this post). Wikipedia says that a solution exists sometimes when the divisors are not pairwise coprime, in particular, in this case, where all remainders are equal. Then a solution can be found using the method of successive substitution.

This problem is much easier because it has a single remainder 3 for all divisors. Therefore, 3 is a solution, though it is not in the given interval [200, 500]. The link for the Chinese remainder theorem above says that all solutions are congruent modulo the least common multiple of the divisors 8, 10, 12 and 30, i.e., 120. Therefore, the least solution in the given interval is 3 + 2 * 120 = 243.