Results 1 to 2 of 2

Math Help - mathematics gcd problems

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: mathematics gcd problems

    Quote Originally Posted by gufog1 View Post
    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...

    Quote Originally Posted by gufog1 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Foundations of Mathematics
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 26th 2011, 11:29 AM
  2. CST (04) in Mathematics?
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 9th 2010, 06:38 PM
  3. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2008, 06:27 AM
  4. mathematics mechanics help
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: February 23rd 2008, 11:17 AM
  5. Mathematics Of Degree (the New Mathematics !!!! )
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: August 26th 2006, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum