Greatest common divisor question

  • #1

Homework Statement



(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.

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
 

Answers and Replies

  • #2
42
0
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
Sorry I don't understand where the 67 is coming from. That confused me in the note too
 
  • #4
42
0
You wrote that gcd(M, 2010) = 335, 402, 670, 1005 or 2010. Notice that all of these numbers are multiples of 67.
 
  • #5
Oh got it, thanks for the help!
 

Related Threads on Greatest common divisor question

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
895
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
19
Views
5K
Replies
11
Views
4K
  • Last Post
Replies
3
Views
1K
Replies
0
Views
1K
  • Last Post
Replies
8
Views
1K
Top