1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Greatest common divisor question

  1. Feb 4, 2010 #1
    1. The problem statement, all variables and given/known data

    (b) Suppose a certain student’s ID number M satisfies
    gcd(M, 2010) > gcd(M, 271) > 1.
    Find all possible values for gcd(M, 2010). Be sure to explain your reasoning. [Note:
    both 271 and 67 are prime.]
    (c) Suppose that the ID number M from part (b) lies between 10020000 and 10030000.
    Find M. Be sure to explain your reasoning.

    3. The attempt at a solution

    So I got b) (I think), gcd(M, 2010) must be greater than 271, as 271 is prime so gcd(M, 271) must be 1 or 271, and it's greater than 1. So I found all the divisors of 2010 which are greater than 271. (Being 2010, 1005, 670, 402, and 335) I think that's correct, though I'm not entirely sure.

    As for c), I really have no idea how to find that, and was hoping for a nudge in the right direction
     
  2. jcsd
  3. Feb 4, 2010 #2
    You know that M is a multiple of both 271 and 67. So M = 67 * 271 * k, for some integer k. You also have 10020000 <= M <= 10030000. What does this tell you about k?
     
  4. Feb 4, 2010 #3
    Sorry I don't understand where the 67 is coming from. That confused me in the note too
     
  5. Feb 4, 2010 #4
    You wrote that gcd(M, 2010) = 335, 402, 670, 1005 or 2010. Notice that all of these numbers are multiples of 67.
     
  6. Feb 4, 2010 #5
    Oh got it, thanks for the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest common divisor question
  1. Greatest common divisor (Replies: 19)

  2. Greatest common divisor (Replies: 24)

Loading...