Problem 25 on math GRE

[jamilabella20]

Hi

in one of the GRE MATH EXAM

there is the following question :

let x and y be postive intergers such that 3x+7y is divisible by 11. which of the following must also be divisible by 11.

option are

a- 4x+6y

b- x+y+5

c- 9x+4y

d- 4x-9y

e- x+y-1

please let me know you reasoning

thanks a lot

[remember]

It's d) 4x-9y....

if we take x = 10, y = 2, then 4x -9y = 22 which is divisible by 11,

if we take x = 14, y = 5 then both 3x + 7y and 4x - 9y are divisible by 11.

if we take x = 18, y = 8, then also both 3x + 7y and 4x - 9y are divisible by 11.

so i think it is D.

[jamilabella20]

thanks so much for replying

iam just curious about how did you set the choice of numbers ?

thanks again

[Macken]

If 3x+ 7y be divisible by 11 they must be separately divisible by 11 as well . So 3x is divisible by 11 and so also 7y.

 

But since 3 and 7 are no multiples of 11, x and y must be.

This implies any Ax +/- By will be divisible by 11

[rr00676]

If 3x+ 7y be divisible by 11 they must be separately divisible by 11 as well . So 3x is divisible by 11 and so also 7y.

 

But since 3 and 7 are no multiples of 11, x and y must be.

This implies any Ax +/- By will be divisible by 11

 

 

this is not correct

 

If both 3x and 7y are divisible by 11, then both x and y and any linear combination of the 2 are divisible by 11 yes. HOWEVER, if 3x+7y is divisible by 11 doesn't imply both 3x and 7y are divisible by 11, it means that the sum of their remainders (when each is divided by 11) is divisible by 11. note that (5,1) is in the set of solutions. Neither 5 or 1 is divisible by 11.

 

The easiest way to do this problem is to take a few point and eliminate. (5,1) eliminates A,C and E. (60,1) eliminates B, so D is our answer. note that (5*12k,1) does the trick was well

 

Review modulus and congruency classes.

[rr00676]

note that (5*12k,1) does the trick was well

 

disregard that...been over 4 years since 've taken an Algebra class

[DWarrior]

a) 4x+6y

b) x+y+5

c) 9x+4y

d) 4x-9y

e) x+y-1

 

You should quickly be able to eliminate options B and E, simply by considering x=y=11. For the other 3, I believe this is the fastest way to do this, unless there is some other trick stemming from the division algo, which I haven't gotten around to reviewing yet:

 

In general, if 3x+7y is divisible by 11, we have two equations:

i) 3x=11q+r

ii)7y=11p-r

 

This means that whatever the remainder for 3x/11 is, 7y/11 must have a remainder (11-r), so that adding the two together yields no remainder.

 

a) To get 4x, take (i) and divide through by 3 and multiply by 4: 4x=(4/3)11q+(4/3)r. Similarly, take (ii) and divide through by 7 and multiply by 6: 6y=(6/7)11p-(6/7)r

 

The sum of the two equations must be divisible by 11, so we should have:

 

4x+6y = (4/3)11q+(4/3)r+(6/7)11p-(6/7)r = 11n

 

Get rid of fractions:

11(7*4q+3*6p)+(7*4-3*6)r = 21*11n

(7*4-3*6)r = 21*11n-11(7*4q+3*6p)

 

The right side is a multiple of 11, and r isn't necessarily (since it's the remainder, in general it won't be).

So we want 7*4-3*6 to be divisible by 11, which it isn't (21-18=3).

 

You can generalize this: given 3x+7y divisible by 11, ax+by is always divisible by 11 only if 7a-3b is divisible by 11.

 

Now you get the other two by simply plugging it in:

c) 7*9-3*4=63-12=51, no

 

d) 7*4x-3*(-9)=28+27=55=11*5, yes!

 

Answer is d

 

When I was actually doing this though, I ended up writing it out for all of them since I didn't see the 7a-3b simplification.

[hakobyant]

In my opinion, this is an easy question! Just take x=y=0 and take out the answers b) and e). Then take x=5 and y=1 (so 3x+7y=3*5+7=22) and take out answers a) and c). That is why the answer is d).

Also 4x-9y=5*(3x+7y)-11x-4*11y.

[twohundredping]

In my opinion, this is an easy question! Just take x=y=0 and take out the answers b) and e). Then take x=5 and y=1 (so 3x+7y=3*5+7=22) and take out answers a) and c). That is why the answer is d).

Also 4x-9y=5*(3x+7y)-11x-4*11y.

 

It is important to note that the question states that x and y are positive integers so you shouldn't (without proper reasoning) plug in 0 for x or y. Now because divisibility works the way it does, it doesn't matter if you plug in positive numbers, negative numbers, or 0. Anyway, I just came here to post a systematic approach.

 

Start with the equation in the premise: 3x + 7y is divisible by 11.

I will work this problem modulo 11. We can always add or subtract a multiple of 11 modulo 11 and get an equivalent expression.

3x + 7y = 0 (mod 11) (Now I want to eliminate the coefficient on x; alternatively, I could have done this for y)

4 * (3x + 7y) = 0 (mod 11)

x + 6y = 0 (mod 11)

 

Now the idea is to multiply this equation by the coefficient on x in each answer and see if I can get the same equation as in the answer.

 

A)

4 *(x + 6y) = 4 * 0 (mod 11)

4x + 2y = 0 (mod 11)

Since there is no way to manipulate 2y mod 11 to make it 6y mod 11 we can eliminate this answer choice. Alternatively, we could have eliminated this answer choice at the beginning since the 6y's matched and there is no way to turn the x mod 11 into 4x mod 11.

 

B)

x + 6y = 0 (mod 11)

There is no way to manipulate 6y mod 11 to make it y + 5 mod 11 so we can eliminate this choice

 

C)

9 * ( x + 6y) = 9 * 0 (mod 11)

9x + 10y = 0 (mod 11)

There is no way to manipulate 10y mod 11 into 4y mod 11

 

D)

4 * (x + 6y) = 4 * 0 (mod 11)

4x + 2y = 0 (mod 11) (Now notice that the coefficient on y in the answer is negative)

4x + 2y - 11y = 0 (mod 11)

4x - 9y = 0 (mod 11)

 

Since we started with the equation we knew to be true and obtained the same equation as D then we know that answer choice D is correct.