# Thread: Rational Number Proof & GCD (Discrete Mathematics)

1. ## Rational Number Proof & GCD (Discrete Mathematics)

Hi,
I'm having quite a lot of trouble with this proof. I can't even determine if this statement is true or false!
Q represents the set of rationals.
Z represents the set of integers.

∀q ∈ Q ∃r ∈ Q so that q + r ∉ Z and qr ∈ Z.

I think this is false because if q happened to be 1/1, then there's no r that satisfies the condition.

The negation would be:
∃q ∈ Q ∀r ∈ Q so that q + r ∈ Z or qr ∉ Z.

But I find this to be false too because there's no such number q that adds with any rational to make an integer, but also multiplies out to a non-integer.

My second question is:
gcd(M, 2010) > gcd(M, 271) > 1.
Find all possible values for gcd(M, 2010).

The gcd(M, 271) can only have the values of 271 or 1 since 271 is odd. But it has to be greater than one, so by elimination, gcd(M, 271) must be 271.

Now am I correct in doing the following? :
2010 * 271 to get 544710, because this number M must have a common divisor between 271 and 2010. Thus the value of gcd(M, 2010) is 2010?

Suppose that the number M lies between 10020000 and 10030000.
Find M. Be sure to explain your reasoning.

I'm really lost on this one, so can someone help me with this please?
My answer so far is taking multiples of 544710 and trying to get it into the range of 10020000 and 10030000, but since I can't do that, there is no possible value for M?

2. gcd(M, 2010) > gcd(M, 271) > 1.
Find all possible values for gcd(M, 2010).
Firstly, 271 is a prime number, secondly to satisfy the condition you need to find M = 271 x a, choose smallest value of 'a' such that 2010 must be divisible by 'a' and 'a' must be greater than 271.
Eg. M = 271 x 335 = 90785

gcd(90785,271) = 271
gcd(90785,2010) = 335

335 > 271 > 1

3. Thanks for the help.
I'm kind of getting what you're saying, but I'm not sure how to find the lowest value of a. I used a calculator and eventually found that your example is the lowest possible a, but I'm not sure how to find it manually and efficiently (for quizzes and tests).
And since M is 90785, all the possible values of gcd(M, 2010) is multiples of 335?

4. The easiest way is to find factors. In this case you need to find values between 271 & 2010. 2010 has 2, 3, 5, 67 as prime factors. so you can find the value of M by choosing combinations of these factors that result in a number >271 and then multiply by 271.
90785 = 67 x 5 x 271, next one can be 108942 = 67 x 6 x 271.

5. Oh I see now! Thank you!

Can someone help me on the other problems now?