Greatest common divisor question

Click For Summary

Homework Help Overview

The problem involves finding the greatest common divisor (gcd) of a student's ID number M with respect to the numbers 2010 and 271, under specific conditions. The context includes determining possible values for gcd(M, 2010) and identifying the ID number M within a defined range.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants discuss the implications of the gcd conditions and explore the relationship between M, 2010, and 271. There is an attempt to identify divisors of 2010 that meet the criteria. Questions arise regarding the relevance of the number 67 and its connection to the problem.

Discussion Status

The discussion is ongoing, with some participants providing insights into the relationship between M and its divisors. There is a recognition of the need for clarification regarding certain elements, such as the role of 67. Guidance has been offered regarding the structure of M in relation to its divisibility.

Contextual Notes

Participants are working within the constraints of the problem statement, which specifies that M must lie within a certain numerical range and that both 271 and 67 are prime numbers. There is an acknowledgment of confusion regarding the inclusion of 67 in the discussion.

DanielJackins
Messages
39
Reaction score
0

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

Similar threads

Can anyone please review/verify this proof of greatest common divisor?
  • · Replies 2 ·
Replies
2
Views
2K
Can anyone please review/verify my proofs for gcd problem?
  • · Replies 4 ·
Replies
4
Views
3K
What is the Greatest Common Divisor of Two Polynomials?
  • · Replies 3 ·
Replies
3
Views
2K
A proof involving the greatest common divisor
  • · Replies 11 ·
Replies
11
Views
5K
Proof About Greatest Common Divisors
  • · Replies 8 ·
Replies
8
Views
2K
What Is the Flaw in This Proof of the Greatest Common Divisor?
  • · Replies 2 ·
Replies
2
Views
2K
Greatest Common Divisor Theorems definition clarification.
  • · Replies 1 ·
Replies
1
Views
2K
Is x^y the Greatest Common Divisor of (5x+3y) and (13x+8y)?
  • · Replies 5 ·
Replies
5
Views
2K
Intro to Proofs: Greatest Common Divisors
  • · Replies 2 ·
Replies
2
Views
2K
Greatest common divisor proof
  • · Replies 9 ·
Replies
9
Views
2K