# Greatest common divisor question

1. Feb 4, 2010

### DanielJackins

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. Feb 4, 2010

### Mandark

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?

3. Feb 4, 2010

### DanielJackins

Sorry I don't understand where the 67 is coming from. That confused me in the note too

4. Feb 4, 2010

### Mandark

You wrote that gcd(M, 2010) = 335, 402, 670, 1005 or 2010. Notice that all of these numbers are multiples of 67.

5. Feb 4, 2010

### DanielJackins

Oh got it, thanks for the help!