Lesson: Introduction to Divisibility

Comment on Introduction to Divisibility

Whoa! Ok, I'm going to need a little more clarification here than most, if you don't mind.

N = 10^40 + 2^40. 2^k is a divisor of N, but 2^(k+1) is not a divisor of N. If k is a positive integer, what is the value of k−2?

Thanks
gmat-admin's picture

Happy to help, bertyy!

You're referring to my question here: https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.html

This is a VERY tricky question (750+)

I have a step-by-step solution here: https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.htm...

Rather than repeat the entire solution, can you take a look and tell me which parts you'd like me to cllarify?

Hi Brent,

Factoring the first part is not the problem or seeing that "5" to the power of anything ends in five. The rest after that just throws me for a loop as to what to do or what is even going on. Usually I can force it after a while and come back to it, but this one has got me blocked. I can't figure out what i'm missing or that some concept that has escaped me.

Thanks for your help
gmat-admin's picture

Okay, I'll elaborate on my solution at https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.htm...

WE have : N = 2^40(5^40 + 1)

We know that 5^40 must end in 25. So, we can say 5^40 = XXXX25 (the X's represent other digits on the number, but we don't really care about them.

So, we can say: N = = 2^40(XXXX25 + 1)

XXXX25 + 1 = XXXXX26 (if we add 1 to a number that ends in 25, the resulting value will end in 26

So, N = (2^40)(XXXX26)

At this part, we need to recognize that since XXX26 is EVEN. So, we can rewrite XXX26 as (2)(XXXX3).

So, N = (2^40)[(2)(XXXX3)]

We can now combine 2^40 and 2. We have: (2^40)(2) = (2^40)(2^1) = 2^41

So, N = (2^41)[XXXX3]

Since XXXX3 is an ODD number, we cannot factor any more 2's out of it. In other words, since XXXX3 is ODD, there are no 2's hiding in the prime factorization of XXXX3.

However, we DO know that there are 41 2's hiding in the prime factorization of 2^41. This means that 2^41 IS a factor of N, but 2^42 is NOT a factor of N.

The question tells us that 2^k is a factor of N, but 2^(k+1) is NOT a factor of N

In other words, k = 41

What is the value of k-2?

Since k = 41, we can conclude that k - 2 = 41 - 2 = 39

Does that help?

Cheers,
Brent

Hi Brent,

what does this factorial expression mean 13!/7!....
Thanks
Fatima-Zahra


gmat-admin's picture

Good question, Fatima-Zahra

This concept appears later, in the counting module (here's the video that covers this notation: https://www.gmatprepnow.com/module/gmat-counting/video/780 )

In general, n! = (1)(2)(3)(4).....(n-1)(n)

For example: 4! = (1)(2)(3)(4) = 24
And 7! = (1)(2)(3)(4)(5)(6)(7) = 5040

Cheers,
Brent

Hi Brent,
I am referring to question https://gmatclub.com/forum/for-any-positive-integer-x-the-2-height-of-x-is-defined-to-be-the-207706.html

I cannot wrap my mind around terminology here "2-height of x", English is not my native language, so when I read "2-height of x", I am thinking of height as in "height of a person", is it a special math terminology "2-height of a number", or we are getting that 2-height is a number of 2s in a positive integer x, because we are given that it is defined such that x=2^n.

In other words, can we have something like 3-height of an integer, 7-height of an integer? I see such terminology for the first time... Thanks a bunch!
gmat-admin's picture

Question link: https://gmatclub.com/forum/for-any-positive-integer-x-the-2-height-of-x-...

The term "2-height" is something the test-makers made up to create this question. We can think of this question as a Strange Operator question, since we're presented with a new term and a definition of that term (more here: https://www.gmatprepnow.com/module/gmat-algebra-and-equation-solving/vid...)

GIVEN: For any positive integer x, the 2-height of x is defined to be the greatest non-negative integer n such that 2^n is a factor of x.

Example: If x = 24, what is the 2-height of 24?
According to the definition, the 2-height of 24 is the biggest value of n, so that 2^n is a factor of 24.
24 = (2)(2)(2)(3)
We can see that 2¹ is a factor of 24.
Also, 2² is a factor of 24.
And 2³ is a factor of 24.
However, 2⁴ is NOT a factor of 24
So, the 2-height of 24 is 3 since 3 is the biggest possible power of 2 that is a factor of 24

Does that help?

Cheers,
Brent

https://gmatclub.com/forum/is-positive-integer-z-greater-than-205456.html
Or it could be the case that z = (3)(7)(13)(2) = 546,....... i could not understand this part (2); how can you multiply 2?
gmat-admin's picture

Link to question and my solution: https://gmatclub.com/forum/is-positive-integer-z-greater-than-205456.htm...

If we know that z is a multiple of 21, then we know that 21 is hiding in the prime factorization of z.
That is, we know that z = (3)(7)(?)(?)(?)(?)
IMPORTANT: The ?'s represent other possible values that might be in the prime factorization of z.
For example, it could be the case that z = (3)(7)(2)(11)(53)
Or, it could be the case that z = (3)(7)(5)(5)
Etc.
That said, all we can be CERTAIN of is that there's a 3 and a 7 hiding in the prime factorization of z

Likewise, if we know that z is a multiple of 39, then we know that 39 is hiding in the prime factorization of z.
That is, we know that z = (3)(13)(?)(?)(?)(?)

When we COMBINE the statements, we know that z MUST have (at the very least) a 3, a 7 and a 13 in its prime factorization.
So, it COULD be the case that z = (3)(7)(13)
Or it COULD be the case that z = (3)(7)(13)(2)
Or it COULD be the case that z = (3)(7)(13)(11)(2)(5)...etc.

Notice that, if z = (3)(7)(13)(2), then it's still divisible by 21, AND it's still divisible by 13
So, z = (3)(7)(13)(2) also satisfies both statements.

Likewise, if z = (3)(7)(13)(11)(2)(5), then it's still divisible by 21, AND it's still divisible by 13
So, z = z = (3)(7)(13)(11)(2)(5) also satisfies both statements.

etc.

Does that help?

Cheers,
Brent

Thanks a ton sir

https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.html
most time i rely on your explanations as maximum are easy to understand. but this one is little bit tough to digest.................

IMPORTANT: we need to recognize that 5^b will end in 25 for all integer values of b greater than 1.
For example, 5^2 = 25
5^3 = 125
5^4 = 625
5^5 = 3125
5^6 = XXX25etc....( is it a kind of concept that 5^(any power,last digits will be 5)?

secondly, = 2^40[2(XXXX3)] [Since XXX26 is EVEN, we can factor out a 2]
= 2^41[XXXX3] ; how you make 2^41 ? ..thanks in advance
gmat-admin's picture

Question link: https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.html

KEY CONCEPT: A x (B x C) = (A x B) x C
For example, 3 x (2 x 5) = (3 x 2) x 5

Now, let's keep going from the part when I say that: N = 2^40[2(some number ending in 3)]

Take: N = 2^40[2(some number ending in 3)]
Use key concept to rewrite this as: N = (2^40 x 2)(some number ending in 3)
Rewrite 2 as 2^1 to get: N = (2^40 x 2^1)(some number ending in 3)
Simplify to get: N = (2^41)(some number ending in 3)

Does that help?

Cheers,
Brent

Hi Brent, I have one question from GMAT Official Guide 2019, question 298 statement one, why c = f, and a = b = 1? Thanks x
gmat-admin's picture

Question link: https://gmatclub.com/forum/each-entry-in-the-multiplication-table-above-...

This official solution doesn't say that it MUST be the case a = b = 1. It just note that this COULD be the case.

That is, if c = f, then it COULD be the case that c = f = 2 and a = b = 1. In this case, the answer to the target question is "c = 2."
However, it could also be the case that c = f = 3 and a = b = 1. In this case, the answer to the target question is "c = 3."

Does that help?

Cheers,
Brent

Hi Brent, I have one question from the Official Guide 2019, page 165 question 127, in the answer explanation, I don´t get it why "if n were divisible by 15, then n-20! would be divisible by 15"? Thank you in advance x
gmat-admin's picture

There's a nice divisibility property that says:
If J is divisible by n, and K is divisible by n, then J-K must also be divisible by n.

Since 20! = (20)(19)(18)(17)(16)(15)(14)(13)....(2)(1), we can see that 20! is divisible by 15.

So, if n is divisible by 15 then, according to the above property, n - 20! must also be divisible by 15.

For more on this divisible property watch: https://www.gmatprepnow.com/module/gmat-integer-properties/video/831

Hi Brent,

If n and k are positive integers, is n divisible by 6 ?

(1) n = k(k + 1)(k – 1)
(2) k – 1 is a multiple of 3.

In the statement (1) do I have to worry about k=1, in which case the whole expression k(k + 1)(k – 1)=0,

Do I have to understand that 0 when divided by any existing number except 0 with no remainder, which implies that 0 is divisible by any number?

Thank you in advance,
gmat-admin's picture

You're correct to say that zero is divisible by any integer.
For example we can say that 0 is divisible by 3.

That said, when it comes to divisibility questions, the GMAT usually (probably ALWAYS) restricts values to POSITIVE integers.

Cheers,
Brent

Thank you very much Brent,

I understand now

Is 12 a factor of the positive integer n?

(1) n is a factor of 36.

(2) 3 is a factor of n.

Can i *rephrase* the question like this?

Is n Divided by 12?

1/ 36 divided by n
2/ n divided by 3

If yes, should i follow this technique in exam?? Wouldn’t it kill time?

Thanks in advance Sir.


https://gmatclub.com/forum/is-12-a-factor-of-the-positive-integer-n-253113.html
gmat-admin's picture

Question link: https://gmatclub.com/forum/is-12-a-factor-of-the-positive-integer-n-2531...

I think you mean to use the word DIVISIBLE, as in "36 DIVISIBLE n"

In that case it would be perfectly fine to rephrase everything as:

Is n DIVISIBLE by 12?

(1) 36 is DIVISIBLE by n
(2) n is DIVISIBLE by 3

It's hard to determine which technique is best for you, since different people will feel differently about the easiest way to rephrase the information. Some people prefer "n is a factor of 36" and some prefer "36 is DIVISIBLE by n"

Cheers,
Brent

Is x/y an even integer?

(1) x is even.

(2) y is a factor of x.

My explanation:
1/we Don't know about y
2/ after rephrasing x/y; don't know about y.

After combining 1+2..
Still we DON'T know about x & y.

Rather it' E .... is it a correct explanation?
gmat-admin's picture

I'm a little unclear of what you mean be "after rephrasing x/y; don't know about y."
Can you elaborate?

Also, for statement 1, we need to be careful. Not knowing anything about y won't always make the statement insufficient.
For example, if the question were....

If x and y are INTEGERS, is x/y an even integer?
(1) x is ODD.

...then statement 1 would be sufficient (even if we don't know anything about y)
The reason for this is that, if x is ODD, then x/y can never be even.

Cheers,
Brent

As we saw a line in the last part of the video
X is divisible by y= y is a factor of x
So, in statement (2) i rephrase it in x/y. Is it wrong sir?

& what's the legal approach in statement (1) then as i said we dontknow about y

Thanks
gmat-admin's picture

You're absolutely right to say that "x is divisible by y" is the same as saying "y is a factor of x"

If I understand you correctly, you're also saying that statement 2 can be rephrased as saying "x/y is an integer." This is also correct.

As I mentioned, not knowing anything about y might not always be grounds for concluding a statement is not sufficient. So, to show that statement 1 is not sufficient, I would look for some counterexamples that yielded different answers to the target question. For example:

Target question: Is x/y even?
(1) x is even

CASE I: x = 12 and y = 3. In this case, x/y = 12/3 = 4, and 4 is even. So, the answer to the target question is "YES, x/y is even"
CASE II: x = 12 and y = 4. In this case, x/y = 12/4 = 3, and 3 is not even. So, the answer to the target question is "NO, x/y is not even"
By examining these two possible cases, it is clear that statement 1 is not sufficient.

Does that help?

Hi Brent
If x, y and z are positive integers, is it true that x^2 is divisible by 16?

(1) 5x = 4y
(2) 3x^2 = 8z
How statement 2 is sufficient?
gmat-admin's picture

IMPORTANT CONCEPT: The prime factorization of a perfect square will have an even number of EACH prime

For example: 400 is a perfect square (400 = 20²)
400 = 2x2x2x2x5x5. Here, we have four 2's and two 5's
This should make sense, because the even numbers allow us to split the primes into two EQUAL groups to demonstrate that the number is a square.
For example: 400 = 2x2x2x2x5x5 = (2x2x5)(2x2x5) = (2x2x5)²

Likewise, 576 is a perfect square (576 = 24²).
576 = 2x2x2x2x2x2x3x3 = (2x2x2x3)(2x2x2x3) = (2x2x2x3)²
--------------------------------
Statement 2: 3x² = 8z
Divide both sides by 3 to get: x² = 8z/3

We can now make two conclusions:
1) z must be divisible by 3 (since we know that 8z/3 must be an integer)

2) Since x² = 8z/3 = (8)(z/3) = (2)(2)(2)(z/3), we can see that the prime factorization of x² has AT LEAST three 2's.
In fact, since the prime factorization of a perfect square will have an EVEN number of each prime, we can conclude that the prime factorization of x² has at least FOUR 2's, which means x² must be divisible by 16.

Does that help?

Cheers,
Brent

Hi Brent
Pls explain this
Is the positive integer n a multiple of 24 ?

(1) n is a multiple of 4.
(2) n is a multiple of 6.
gmat-admin's picture

Hi Brent,
Is p is a positive integer, is p^2 divisible by 96?

(1) p is a multiple of 8.
(2) p^2 is a multiple of 12.
Can I know your version of solution for this problem
gmat-admin's picture

Is 12 a factor of the positive integer n?

(1) n is a factor of 36.
(2) 3 is a factor of n.

Is 12 a factor of the positive integer n means Is N divisible by 12?
Am I right?
gmat-admin's picture

That's correct!
In fact there are many different ways to state this information:
12 is a factor of n
12 is a divisor of n
n is divisible by 12
n is a multiple of 12
n/12 is an integer
n = 12k for some integer k

Cheers,
Brent

Hey Brent! I'm looking at your solution for https://gmatclub.com/forum/is-the-product-pqr-divisible-by-216152.html and I'm not understanding how this was deduced
p² - q² = 128
gmat-admin's picture

Solution link: https://gmatclub.com/forum/is-the-product-pqr-divisible-by-216152.html#p...

Good catch! That was part of a solution I cut and pasted from a different solution, but I forgot to edit it.
I've now fixed my solution. Thanks for the heads up!

Hi Brent

Question: N=1040+240N=1040+240. 2k2k is a divisor of NN, but 2k+12k+1 is not a divisor of NN. If k is a positive integer, what is the value of k−2k−2 ?

A) 38
B) 39
C) 40
D) 41
E) 42

i get your explanation to the part of 5^sth will always end in 25, so + 1 will always end in 26, hence the quotient when divided for 2 is always 3 sth. But how does that help us to deduce that k = 41 ? can you explain?
gmat-admin's picture

Question link: https://gmatclub.com/forum/n-10-40-2-40-2-k-is-a-divisor-of-n-237383.html
In the future, please provide a link to the question on GMAT Club (there were formatting issues with your post)

Let's start here: N = (2^40)(XXXX26)
Factor out a 2 out of XXXX26 to get: N = (2^40)(2)(XXXXX3)
Simplify to get: N = 2^41(XXXXX3)

Since XXXXXX3 is clearly odd, we can be certain that we can't factor out any more 2's out of XXXXXX3.

We're told 2^k is a divisor of N, but 2^(k+1) is not a divisor of N
Since N = 2^41(XXXXX3), it must be the case that k = 41.

This satisfies the condition that 2^k is a divisor of N, but 2^(k+1) is not a divisor of N.
That is, 2^41 is clearly a divisor of 2^41(XXXXX3)
But 2^42 is not a divisor of 2^41(XXXXX3)

So, k must equal 41.

Does that help?

ah got it! thank you!

Tweet about the course!

If you're enjoying this GMAT video course, help spread the word on Twitter.

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.

Have a question about this video?

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

Free “Question of the Day” emails!