Primes Question

[valkener]

"If y is divisible by 12 and 10, is y divisible by 24?"

Now, I could solve this through plugging in but investigating the prime factors is easier:

12: 2, 2, 3

10: 2, 5

24: 2, 2, 2, 3

The answer is: NO. However, I don't get why not given the fact that 10 and 12 have the neeccessary prime factors (2, 2, 2, 3).

Please help me understand. :-)

[are we there yet?]

one strategy is just to test #s...

Make y=60. Is it divisible by 10 and 12? Yes. Now, is 60 divisible by 24? No. The question is asking whether this divisibility relationship will always hold true. As you can see it does not.

[vonLipwig]

If a number is divisible by a and b, then it is divisible by lcm(a,b ). (Lowest common multiple). It is not necessarily divisible by the product ab. For example, 60 is a multiple of 12 and of 10, but is not a multiple of 120. Similarly, looking at the powers of two, something that is a multiple of 4 and a multiple of 2 doesn't need to be a multiple of 8. (For example, the number 4). This is the issue in this question.

Edited November 9, 2012 by vonLipwig

[R Deckard]

24 is a multiple of 2*2*2 = 8. 10 is not. 12 is not. You can't combine factors like that. Consider this: an even number is divisible by 2 and 2, but not necessarily 4.

[valkener]

Thanks I understand it must not be true but I was looking for an answer that refers to the prime factorials. That's the methodology I am working on for these kind of problems right now and it's important for me to us this method properly/

[iowaguy]

I don't think using prime factors is a good way to try to deduce divisibility. Let's reword your original question:

"If y is divisible by 12 and 2, is y divisible by 24?"

12: 2, 2, 3

2: 2

24: 2, 2, 2, 3

Here you can see that, even though the sum of the prime factors of 12 & 2 equals the sum of the prime factors of 24, a number divisible by 12 and 2 (for example, the number 36) is not necessarily divisible by the number 24. A better approach, IMHO, is to plug & chug numbers and test their divisibility. And it's also faster to do so, which is always the best strategy on the GRE.

[TakeruK]

I agree with those that say checking is an easier way to do this. But, if you really want to do it with prime factors, then here is what I THINK is right.

Since the prime factors of 24 are (2,2,2,3), then a number has to have ALL of these prime factors in order to be divisible by 24. That is, all numbers divisible by 24 are also multiples of 24, which means you can write their prime factors as (2,2,2,3, ....[whatever else]).

However, for "y", which is divisible by 12 and 10, and they have prime factors:

12 --> (2,2,3)

10 --> (2,5)

Y just has to have any set of prime factors that satisfies both. For example 60 = (2,2,3,5) is a valid number for "y" because it meets the divisibility by 12 (i.e. it has ALL the prime factors of 12) and it is also divisible by 10 (also has ALL the factors of 10). Note that one of the "2" prime factors is "double counted" but that's okay. However, (2,2,3,5) is NOT divisible by 24 because it does not contain ALL the prime factors of 24 (there are three 2's needed).

Hope that makes sense.

Summary: A number Y is divisible by X if and only if ALL the prime factors of X is present in the prime factorization of Y. If a number Y is divisible by multiple numbers (e.g. A, B, C, etc..) then you just have to make sure the prime factorization of Y contains ALL the prime factors of A, B, C, etc. but you are allowed to "reuse" prime factors for different A, B, C...

And finally, just to do another example:

If y is divisible by 15 and 18, is it divisible by 36?

15 has prime factors (3,5)

18 has prime factors (2,3,3)

The minimum prime factors that y must have are (2,3,3,5). This is the smallest set of numbers you can make that will contain all of the prime factors of 15 and 18 (although not necessarily at the same time).

36 has prime factors (2,2,3,3)

y is then not necessarily divisible by 36 because y's minimum prime factors are (2,3,3,5), which does not contain ALL of the prime factors of 36 (2,2,3,3).

[R Deckard]

I don't think using prime factors is a good way to try to deduce divisibility.

Oh boy.

[valkener]

Take: thanks for the excellent answer. The trick in my initial question is that the 2 is being used twice and thus the answer must be "is not necessarily true. I am coming to the conclusion that looking at prime factors is an excellent way (and fast, easy) to check for divisibility. I actually haven't taken the gre yet so I can't say if this is the ideal method on test day. Opinions?

[iowaguy]

IMHO, the fastest way (apparently Deckard doesn't think so), given the question format you presented, is simply to generate a couple of numbers divisible by both 10 & 12 and test whether they are divisible by 24. By the time you break down the 3 numbers in your original question (10, 12, and 24) into their prime factors, I would have already moved onto the next question by figuring out that 60 (divisible by 10 & 12) is not divisible by 24.

You should always be looking for the fastest, most efficient way to answer a GRE question. There is usually more than 1 way to find the right answer. The GRE quant section is as much a test of your ability to find the fastest method as it is a test of your knowledge of math theory.

Therefore, I don't think breaking numbers down into prime factors is the most efficient way to test for divisibility. YMMV.

Edited November 12, 2012 by iowaguy

[TakeruK]

I think it's important to keep in mind that the way we might have been taught to do these questions in high school math classes are usually not the best way to approach the GRE Quant. questions. I remember in high school, we would have to show all our steps and follow the method exactly to get full points. In the GRE, you just need to get the right answer, no matter how you do it! So, I think it's best to find a method that works the fastest for you and stick with it. This is important on other ETS tests as well -- for example, in the Physics subject GRE, there are many questions where you should not solve it by evaluating equations etc. -- instead, guessing and checking sometimes is the best method.

For me, I would have solved this question by looking for counter-examples first. Anytime I see a question asking about the validity of a mathematical statement that is asserting something to be always true, my first instinct is to find a case where it isn't. It works well in this case because the very first possible value for "y" is the counter-example.

Edit: However, prime factorization will always work I think. So if you get really hard numbers like "if y is divisible by 85 and 92, is it divisible by 96" or something like that, then it would be easier to just prime factorize. But the GRE would not ask you questions with really stupid numbers like that. In addition, the larger the number, the less likely that statement is going to be true since the multiples of both 85 and 92 are few and far between! I would always try a faster method first, and if that doesn't work then resort to prime factorization. It might cost me more time in that one question, but I would save a lot of time for the questions that didn't need a full treatment.

I think it's helpful to have the multiplication table up to 12x12 =144 memorized for the GRE Quant. Then you would have quickly realised that 60 is the lowest common multiple faster than you can prime factorize! Another useful thing to know is the divisibility rules. Here is a list (http://en.wikipedia....visibility_rule) -- I had learned the ones up to divisibility by 10 (except for the rule for 7, it's too complicated).

Edited November 12, 2012 by TakeruK

[valkener]

Take since you are such an excellent resource do you have a compilation of critical formulas for the quant section? And who is the publisher of your choice for prep?

Thanks so much!

[TakeruK]

I'm glad you found my answers useful, but unfortunately I don't have a handy "cheat sheet" of everything one really needs to know for the exam. Since I had to do a lot of math in my physics undergrad degree, I did not prepare very much for the General GRE Quant -- I spent all my time on the Verbal section instead. But I think you can find these things online! I used http://www.majortests.com/ to study for the Verbal part and it worked really well for me. I also did one or two practice worksheets from their math section since I didn't want to underestimate it. I don't know how good their math prep things are, but I really found the Verbal part useful.

However, I should note that I took in the GRE in June 2011, before the new "Revised General GRE" changed everything in August 2011.