Lesson: Divisor Rules

Comment on Divisor Rules

For this question

http://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-integer-k-and-5-and-8-a-3824.html

5 and 2 are factors of K, where as
5 and 2 are not factors of M.

there fore K-M shouldn't be the multiple of 5 and 2 right?
greenlight-admin's picture

Question link: http://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-inte...

If 15 and 4 are factors of positive integer K, and 5 and 8 are not factors of positive integer M, then K – M CANNOT equal

A) 34
B) 44
C) 54
D) 70
E) 83

yogasuhas, you are correct to say that 5 is a factor of K, but 5 is NOT a factor of M.

However, your second statement is not true.
We're told that "8 is NOT a factor of M." This tells us that the prime factorization of M does NOT have three 2's. However, it's still possible that the prime factorization of M has one or two 2's.

For example, 8 is NOT a factor of 12, but 2 IS a factor of 12. Likewise, 4 IS a factor of 12.

Great! Thank you so much.

How did we get the values of k and M
greenlight-admin's picture

For that question, we can't find the actual values of K and M, since they can have infinitely many values.

However, once we conclude that 5 is NOT a factor of K - M, we can check the answer choices and see that K-M cannot equal 70.

Cheers,
Brent

Can you elaborate on how you got 70?
greenlight-admin's picture

Please see my solution at https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...

We have a rule that says:
If d is a factor of x, but d is NOT a factor of y, then d is NOT a factor of x-y

We're told that 5 is a factor of K.
And we're told that 5 is NOT a factor of M

By the above rule, we know that 5 is NOT a factor of K-M
So, since 5 is a factor of 70, we know that K-M CANNOT equal 70

Does that help?

Cheers,
Brent

The source of this question is Argo Brothers, huh? Not a fan of them. Let's look at this reasoning...what can be K? Let's pick 60 because 15 and 4 are both factors of 60. We can agree on that. So we have K = 60. Use the answers along with K - M to start checking what fits.

A) 34. So in other words, K - M = 34. 60 - M = 34. M must be 26. 5 and 8 are not factors of 26, so K - M CAN equal 34. Eliminate.

B) 44. K - M = 44. 60 - M = 44. M = 16. 5 and 8 are not factors of 16. Eliminate.

Now let's make K = 120 because 15 and 4 are factors of 120.

C) 54. K - M = 54. 120 - M = 54. M = 66. 5 and 8 are not factors of 66. Eliminate.

D) 70. K - M = 70. 120 - M = 70. M = 50. 5 and 8 are not factors of 50. ELIMINATE. HUH?!?!?

Toss this one out! If you simply plug in values for K that satisfy the first half of the problem, and then you use the K - M = thing, D really doesn't work. Very bad question.
greenlight-admin's picture

I'm not a big fan of questions created by Argo Brothers either. That said, this is a reasonable question that can be solved quickly if you're familiar with the divisor rules (as I show in my solution at https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...)

For the below question

http://www.urch.com/forums/gre-math/155320-mgre-5lb-book-divisibility-primes.html

24 will have (2)(2)(2)(3) as prime factorization.

Let n³ = x.
If x has to be divisible by 24, it must have 3 number of 2s and 1 number of 3s, right?

In that case x will be divisible by 1, 2, 3, 4, 6, 8, 12, 24

In the given options 12 is largest number E should be the answer, right?
greenlight-admin's picture

For others reading this, here's the question at http://www.urch.com/forums/gre-math/155320-mgre-5lb-book-divisibility-pr...

If n is an integer and n³ is divisible by 24, what is the largest number that must be a factor of n?

(A) 1
(B) 2
(C) 6
(D) 8
(E) 12
-----------------------------
Yes, you are right to say "x will be divisible by 1, 2, 3, 4, 6, 8, 12, 24"

In your solution, you let x = n³. So, you are basically saying that n³ will be divisible by 1, 2, 3, 4, 6, 8, 12, 24. That's all true.

HOWEVER, the question asks us to determine the largest number that must be a factor of n (not n³, aka x)

Brent, am still not clear. Can you please take some number and explain?

how can we find the largest factor of n?
greenlight-admin's picture

Sure thing.

n = 6
If n = 6, then n³ = 6³ = [(2)(3)]³ = (2)(3)(2)(3)(2)(3) = (2)(2)(2)(3)*(3)(3) = 24*(3)(3)
So, when n = 6, we can see that 24 is a factor of n³

The question asks "What is the largest number that must be a factor of n?"

Answer: 6

Great!, but still 6^3 = (2)(3) (2)(3) (2)(3) = (2*2*2*3) (3*3) (i think you have written one 2 extra, isn't it?)

And if n = 12, n^3 = (2*2*3)^3 = (2*2*3) (2*2*3) (2*2*3) = 24*2*2*2*3*3
when n=12 n^3 is divisible by 24. therefore 1,2,3,4,6,12 are factors of n=12.
in those 12 is largest factor. Why cant 12 be the answer?
greenlight-admin's picture

Thanks for the first part (the extra 2). I've edited my response above.

Regarding your point about n = 12 also working (since 24 is also a factor of 12³): Yes, you are correct. However, the question asks "What is the largest number that MUST be a factor of n?"

We've already seen that n = 6 satisfies the given information, so we can't say that 12 MUST be a factor of n.

Brent! finally i tried to understand. It worth mention that following problem helped me a bit along with your explanation.

n^2 is multiple of 24 and 108, which of the following integers are divisors of n?
A) 12
B) 24
c) 36
D) 72

when n^2 is divisible by 24 (2 2 2 3) and 108 (2 2 3 3 3), it implies n^2 must divisible by lcm of 24 and 108 also (2 2 2 3 3 3). We can infer that n will have at lease three 2's and three 3's.

let n = (2^0 3^0) => n^2 = 1 which is not multiple of (2^3 3^3)
let n = (2^1 3^1) => n^2 = (2^2 3^2) which is not multiple of (2^3 3^3)
let n = (2^2 3^2) => n^2 = (2^4 3^4) which is multiple of (2^3 3^3)

then n will be multiple of 2^4 3^4 = 36 (36, 72, 108...). In given option only 12 and 36 are factors of 36. There fore A and C are the answer.

coming to your first question, when n^3 / 24, what would be the largest factor of n?

n^3/24 => n^3/ (2 2 2 3),

let start with n = 0 => 0 is multiple of 24, try with 1,2,3,4,5 all respective cube values will not be multiple of 24.
let n=6 (2 3) => n^3 = (2^3 3^3) which is multiple of 24, therefore we can infer that n must be multiple of 6 (6, 12, 18 ...), I was telling 12 is largest, but 12 can not be the factor of 6!, what we need is the largest factor of the numbers in the set which consists of multiple of 6.

Therefore 6 is the only possible for answer. :) finally!
greenlight-admin's picture

nice work!

Hi Brent ,

in the above explinatio at this line 24*(3)(3)
you meant that

6^3=216 and its factors are 2^3 and 3^3
and in this we are searching for the largest divisor that is divisible by 6
so if we take 4 , it is not a factor of 6 neither 8 and 12
so you have choosen 6

Is this the right approach

Thanks
greenlight-admin's picture

The question: If n is an integer and n³ is divisible by 24, what is the largest number that must be a factor of n?
If n³ is divisible by 24, then 6 is the SMALLEST possible value of n.

So the question becomes, "What is the largest number that must be a factor of 6?
6 is the biggest number that is a factor of 6.
So, the answer is 6

Does that help?

Hey Brent. How do we know that one 2 and 3 are hiding? Thanks
http://www.urch.com/forums/gre-math/155320-mgre-5lb-book-divisibility-primes.html
greenlight-admin's picture

Question link: http://www.urch.com/forums/gre-math/155320-mgre-5lb-book-divisibility-pr...

Let's examine a few values of integer q (these examples are separate from the linked question above)

Let's say q = 20
So, we can say that q = (2)(2)(5)
This also means that q³ = (2)(2)(5)(2)(2)(5)(2)(2)(5)
Notice that the prime factorization of q³ consists of 2's and 5's only. Also notice that the prime factorization of q consists of 2's and 5's only.

Let's try a new value of q.
If q = (3)(7), then q³ = (3)(7)(3)(7)(3)(7)
Notice that the prime factorization of q³ consists of 3's and 7's only. Also notice that the prime factorization of q consists of 3's and 7's only.

One more.
If q = (5)(7)(11), then q³ = (5)(7)(11)(5)(7)(11)(5)(7)(11)
Notice that the prime factorization of q³ consists of 5's, 7's and 11's only. Also notice that the prime factorization of q consists of 5's, 7's and 11's only.

In the question, we're told that n³ is divisible by 24
We can write: n³ = 24k for some integer k
This also means that the prime factorization of n³ = (2)(2)(2)(3)(?)(?)(?)(?)...
If the prime factorization of n³ has some 2's and 3's, then it must also be the case that the prime factorization of n has at least one 2 and one 3.

In other words, we have a 2 and a 3 "hiding" in the prime factorization of n.

Does that help?

Cheers,
Brent

Yes, thanks!!

Brent, I think there's possibly a mistake in your answer choices here.
https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-integer-k-and-5-and-8-a-3824.html

If 15 and 4 are factors of positive integer K, and 5 and 8 are not factors of positive integer M, then K – M CANNOT equal

A) 34
B) 44
C) 54
D) 70
E) 83

If 8 is a factor of M, then we can also be certain that 4 is a factor of K.

So, we know that 4 is a factor of K AND we know that 4 is not a factor of M.

So, the answer choices cannot contain an answer that is divisible by 4. But 44 is divisible by 4.
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...

I'm not sure what you mean by "If 8 is a factor of M, then we can also be certain that 4 is a factor of K."

We're told that 8 is NOT a factor of M. So, I'm not sure what role this plays in your solution.

If you're suggesting that the correct answer could also be B (44) then consider this case:
K = 120 (notice that 15 and 4 are factors of K)
M = 76 (notice that 5 and 8 are NOT factors of M)

K - M = 120 - 76 = 44
Since it's possible that K - M = 44, answer choice B cannot be the correct answer.

Does that help?

Cheers,
Brent

https://gre.myprepclub.com/forum/which-of-the-following-is-a-multiple-of-7614.html

I was thinking of breaking 6 into its prime factors and checking the answers whether they are divisible by 2 & 3 but apparently this is the wrong approach. Whats wrong with my thinking process?
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/which-of-the-following-is-a-multiple-of...

Your reasoning is correct.
Since 6^2 is divisible by 2 and 3, then the correct answer MUST be divisible by 2 AND 3.
When we check the answer choices, we can eliminate A, B and E.

So, the remaining answer choices are C and D

Well, since 6^2 is also divisible by 9, the correct answer MUST be divisible by 9
When we check the answer choices, we can eliminate C.

Does that help?

Cheers,
Brent

Yes it helps but I want some clarification. I understand that when we take the prime of 36 we get 2x2x3x3 as its prime factors. So in order to check whether a given number is a multiple we need to check whether it is divisible with the all the possible combination of integers as in this case: 2,4,6,9,12?
greenlight-admin's picture

We're looking for a multiple of 36.
If a number is a multiple of 36, then that number must be divisible by all factors of 36 (1, 2, 3, 4, 6, 9, 12, 18 and 36)
So, we can first start by eliminating answer choices that are NOT divisible by 2.
Then we can eliminate answer choices that are NOT divisible by 3.
If there are answer choices remaining we can check other factors of 36.
etc . . . until we're left with 1 answer choice.

Does that help?

Cheers,
Brent

Thanks makes a lot of sense now

http://www.urch.com/forums/gre-math/155320-mgre-5lb-book-divisibility-primes.html in this question isn't the answer supposed to be 8 since 2x2x2 is also present and greater than 6
greenlight-admin's picture

Be careful, there are three 2's present in n³ (not n)
So, all we can conclude is that there must be at least ONE 3 present in n.

Cheers,
Brent

Thanks so much Brent.. please in regards to the last question https://gre.myprepclub.com/forum/30-20-20-20-is-divisible-by-all-of-the-9508.html , if we factorize 10^20, how do we still have 3^20 and 2^20 instead of just 2 and 3.
thanks
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/30-20-20-20-is-divisible-by-all-of-the-...

There's a nice exponent law that says: (jk)^n = (j^n)(k^n)
So, 30^20 = (10 x 3)^20 = (10^20)(3^20)

To see why this is, let's factor a simpler expression: 30^5

Take: 30⁵ = (30)(30)(30)(30)(30)
Now rewrite each 30 as (10)(3).
We get: 30⁵ = (10)(3)(10)(3)(10)(3)(10)(3)(10)(3)
Rearrange to get: 30⁵ = (10)(10)(10)(10)(10)(3)(3)(3)(3)(3)
Rewrite as follows: 30⁵ = (10⁵)(3⁵)

Does that help?

Cheers,
Brent

Thanks so much it really does

Hi Brent,

In cases where denominator is > numerator, what is the remainder? For example:- When 5 is divided by 8, is the remainder 5? Please clarify. Thanks.
greenlight-admin's picture

That's correct.

5 divides into 8 zero times with remainder 5
Likewise, 11 divided by 20 equals zero with remainder 11

In general, if x < y, we can write:
x divided by y equals zero with remainder x

Cheers,
Brent

Hello Brent,
can you please break down the solution for the question "https://gre.myprepclub.com/forum/which-of-the-following-is-a-factor-of-2107.html " for me. Thank you.

Hi Brent,

In the above while explaining that:
5 is a divisor of 35 -> 5 is divisor of of product of 35 and 47
From where does this 47 came into picture

Thanks
greenlight-admin's picture

That's just one example of the property: If k is a divisor of M, then k is a divisor of NM

More examples:
- Since 12 is a divisor of 36, we know that 12 must be a divisor of (36)(101)
- Since 11 is a divisor of 77, we know that 11 must be a divisor of (77)(28)
- Since 3 is a divisor of 21, we know that 3 must be a divisor of (21)(587)

Does that help?

Cheers,
Brent

Hi Brent,

Regarding the question : https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-integer-k-and-5-and-8-a-3824.html

I cant rememeber that theory part ecaxtly so I did in this way
K=60
M=12
and could you please let me know the way to proceee further

Thank You
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...

If 15 and 4 are factors of positive integer K, and 5 and 8 are not factors of positive integer M, then K – M CANNOT equal
A) 34
B) 44
C) 54
D) 70
E) 83
--------------------------------------
You're correct to say that K = 60 and M = 12 satisfy the conditions that "15 and 4 are factors of positive integer K, and 5 and 8 are not factors of positive integer M"
This means K - M = 60 - 12 = 48
So, IF it were the case that 48 was among the answer choices, then we could have eliminated that answer choice, since it is possible for K - M 2 equal 48.

KEY IDEA: K = 60 and M = 12 is just ONE pair of values that satisfy the conditions.

It could also be the case that, K = 60 and M = 26 (since 5 and 8 are not factors of 26)
In this case, K - M = 60 - 26 = 34
So, we can ELIMINATE answer choice A

It could also be the case that, K = 60 and M = 6 (since 5 and 8 are not factors of 6)
In this case, K - M = 60 - 6 = 54
So, we can ELIMINATE answer choice C

As you can see, to eliminate four of the five answers choices, we'll need to test a lot of values.
So, if we continue this approach, it's going to take us a very long time to answer the question.

However if we apply the divisor rules (as I did here https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...), we can answer the question in a matter of seconds.

Cheers,
Brent

https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-integer-k-and-5-and-8-a-3824.html

A) 34
If K = 60 and M = 26, then K - M = 34
ELIMINATE A



B) 44
If K = 120 and M = 76, then K - M = 44
ELIMINATE B


C) 54
If K = 60 and M = 6, then K - M = 54
ELIMINATE C

E) 83
If K = 120 and M = 37, then K - M = 83
ELIMINATE E


As I understood (15)(4) =60 = k BUt I don't know how did you get 120= k ?
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/if-15-and-4-are-factors-of-positive-int...

We're told that "15 and 4 are factors of positive integer K, and 5 and 8 are not factors of positive integer M"
So, some possible values of K include: 60, 120, 180, 240, 300, etc

Our goal is to eliminate 4 of the 5 answer choices.
To eliminate answer choice E, we must find values of K and M such that K – M = 83
We know that M is positive, so if we try to let K = 60, then K-M will be less than 60

So, in order to find values of K and M such that K – M = 83, we can't start with K = 60
So, I tested K = 120 (which is also an allowable value of K)

Cheers,
Brent

Hi Brent, I have a question on this: https://gre.myprepclub.com/forum/when-the-positive-integer-n-is-divided-by-3-the-remainder-i-13634.html

Can this be solved by the other division method? (Where you create an equation)
greenlight-admin's picture

Question link: https://gre.myprepclub.com/forum/when-the-positive-integer-n-is-divided-...

By "division method," I'm assuming you're referring to the strategy called " rebuilding the dividend" (which starts at 5:27 of the following video: https://www.greenlighttestprep.com/module/gre-integer-properties/video/840)

We can use this approach, but it will be much less effective than the "possible values" approach I used in my solution. That said, let's try...

THE QUESTION: When the positive integer n is divided by 3, the remainder is 2 and when n is divided by 5, the remainder is 1. What is the least possible value of n?

From the given information, we can write:
n = 3k + 2 (where k is a positive integer)
n = 5j + 1 (where j is a positive integer)

Since both equations are set equal to n, we can write: 5j + 1 = 3k + 2
Subtract 3k from both sides of the equation to get: 5j - 3k + 1 = 2
Subtract 1 from both sides of the equation to get: 5j - 3k = 1

At this point, we need to find the SMALLEST positive integer values of j and k that satisfy the equation 5j - 3k = 1
After a little bit of testing, we see that j = 2 and k = 3, are the smallest possible integer values that satisfy the equation.
So to find the value of n, we'll plug j = 2 into our original equation n = 5j + 1 to get n = 5(2) + 1 = 11

Answer: 11

Does that help?

yes! thank you :)

Hi Brent, in this question https://www.urch.com/forums/topic/149582-mgre-5lb-book-divisibility-and-primes/

Is it also 6 if it had asked n^2 is divisible by 24?
greenlight-admin's picture

Thanks Brent for confirmation.

Have a question about this video?

Post your question in the Comment section below, and a GRE expert will answer it as fast as humanly possible.

Change Playback Speed

You have the option of watching the videos at various speeds (25% faster, 50% faster, etc). To change the playback speed, click the settings icon on the right side of the video status bar.

Let me Know

Have a suggestion to make the course even better? Email us today!

Free “Question of the Day” emails!