# Lesson: Counting the Divisors of Large Numbers

## Comment on Counting the Divisors of Large Numbers

### great tip! thank you so much!

great tip! thank you so much!!﻿

### Should we consider 1 as the

Should we consider 1 as the divisor of a number ? ### 1 is a divisor of all

1 is a divisor of all positive integers. However, with respect to the technique described in this video, we wouldn't include 1 in the prime factorization of the number for which we're trying to find the total number of divisors.

For example, to determine the total number of divisors of 14000, we first prime factorize 14000 to get 14000 = (2^4)(5^3)(7^1)

We wouldn't write: 14000 = (1^1)(2^4)(5^3)(7^1)

We wouldn't do this because 1 is NOT a prime number, so it has no place in the PRIME factorization of a number.

Also, including 1 would be problematic, because the exponent could be ANY number.

For example, 12 = (1^1)(2^2)(3^1) or 12 = (1^4)(2^2)(3^1) or 12 = (1^33)(2^2)(3^1) etc.

Does that help?

### Hi Brent,

Hi Brent,

1 is actually included in the total number of suitable devisors. Let me explain:

When we take the number 6 and try to go through your technique we get this:

6=(2^1)*(3^1)→ the number of divisors is: 2*2=4↓

(2^1)*(3^1)=2*3=6
(2^1)*(3^0)=2*1=2
(2^0)*(3^1)=3*1=3
(2^0)*(3^0)=1*1=1

And I think that this is how it should work since the question ask you about "how many positive divisors?" and not "how many positive prime factors". Since 1 is a positive divisor, despite not being a prime factor, it must be included in the answer choice, and it is.

Am I right? ### You're absolutely correct. 1

You're absolutely correct. 1 IS included in the total number of suitable DIVISORS.
That's what I state in my comment above.

I say that we don't include 1 in the PRIME FACTORIZATION of the number for which we're trying to find the total number of divisors.

So, as you note:
6 = (2^1)(3^1) [we don't include 1 in the PRIME FACTORIZATION of 6]
Yes, (2^0)(3^0)= (1)(1) = 1 [1 one of the DIVISORS of 6]

Cheers,
Brent

### What is the rationale behind

What is the rationale behind adding 1 to each exponent/ raising each prime factor to 0? ### I cover this a 1:50 in the

I cover this a 1:50 in the video.

We add 1, because we must also consider the possibility that the exponent is 0.

So, for example, if 2^5 is in the prime factorization of N, then when it comes to possible divisors of N, we must consider 2^5, 2^4, 2^3, 2^2, 2^1 and 2^0.
So there are 5+1 possible exponents.

### I got 30 positive divisors

I got 30 positive divisors for 1008, but I cant seem to get the other two right. Can you show me how you got 16 divisors for 3375, and 49 for 100 000?

I got 20 for 3375 and 36 for 100 000. Where am I going wrong? Hmm. ### 3375 = (3)(3)(3)(5)(5)(5) =

3375 = (3)(3)(3)(5)(5)(5) = (3^3)(5^3)
So, the number of divisors = (3+1)(3+1) = 16

1,000,000 = (2)(2)(2)(2)(2)(2)(5)(5)(5)(5)(5)(5) = (2^6)(5^6)
So, the number of divisors = (6+1)(6+1) = 49

Does that help?

Cheers,
Brent

### Hi Brent,

Hi Brent,

Need a little clarification on this problem:

For a certain positive integer N, N³ has exactly 13 unique factors. How many unique factors does N have?
A. 1
B. 2
C. 3
D. 4
E. 5

Specifically, I don't get this part of the rationale: "So, a number with 13 positive divisors must have a prime factorization that looks like this: prime^12"

What I'm I not seeing? RULE: if integer N = (p^a)(q^b)(r^c)(etc), where p, q, r etc are prime numbers, then the number of factors of N = (a + 1)(b + 1)(c + 1)...etc

Notice that the number of factors of N equals the PRODUCT of all of the exponents increased by 1.

So, if we say that the number N^3 has 13 factors, then the PRODUCT of all of the exponents (increased by 1) of N^3 must equal 13.

However, there is only ONE WAY to write 13 as a product. That is: 13 = 13 x 1

So, it must be the case that N^3 = p^12 (where p is some prime number)

Let's confirm this.

When we apply the above RULE, we see that the number of factors of N^3 = (12 + 1) = 13

So, if N^3 = p^12 (where p is some prime number), then we can also conclude that N = p^4.

So, if N = p^4, then we can apply the RULE to conclude that the number of factors of N = (4 + 1) = 5

Does that help?

Cheers,
Brent

### Brent, if you wouldn't mind

Brent, if you wouldn't mind providing an example that would be great because I am severely blocked on this question. Something I am not seeing or getting is really frustrating me here.

Thanks ### No problem.

No problem.

Let's say I tell you that integer K has 12 positive factors.

Since there are many way to get a PRODUCT of 12, there are many possible ways to write K.

K COULD = (p^2)(q^3) [where p and q are prime numbers].
When we apply our earlier RULE, the number of positive factors of K = (2 + 1)(3 + 1) =(3)(4) = 12. Works!

Or K COULD = (p^1)(q^5) [where p and q are prime numbers].
When we apply our earlier RULE, the number of positive factors of K = (1 + 1)(5 + 1) =(2)(6) = 12. Works!

Or K COULD = (p^11) [where p is a prime number].
When we apply our earlier RULE, the number of positive factors of K = (11 + 1) = 12. Works!

Since there are many ways to get a product of 12, there are several different ways to write K: K = (p^2)(q^3), K = (p^1)(q^5) and K = (p^11)

However, since there is only 1 way (using positive integers) to get a product of 13, then there is only 1 way to write N^3

If MUST be the case that N^3 = p^12 (where p is some prime number)

Does that help?

Cheers,
Brent

### Hi Brent for the above

Hi Brent for the above explanation, how can we conclude that N=P? ### Oops, my mistake.

Oops, my mistake.
That was supposed to read N = p^4
Thanks for catching that! I have edited my response accordingly.

Cheers,
Brent

### Hi Brent,

Hi Brent,

720 = 2^4 * 3^2 * 5^1

While I understood the application of the fundamental counting principle to arrive at the number of divisors of 720, I want to know what is wrong in the below approach

There are three positions to be filled and we have 10 choices - 2^0, 2^1, 2^2, 2^3, 2^4, 3^0, 3^1, 3^2, 3^3, 5^0, 5^1, 5^2

Isn't this a combinatorics problem where I have to make a selection of 3 from 10 where the order does not matter (since 2^0 * 3^2 * 5^1 = 5^1 * 2^0 * 3^2) ?

10C3 is 120 which does not tally with the answer derived using the fundamental counting principle. Where am I going wrong? ### There are two main problems

There are two main problems with your solution:

1) Why are you selecting 3 of the 10 choices?
Selecting 1 choice (2 or choices) will also be a factor of 720

2) There's some duplication in the outcomes.
For example, one possible outcome is selecting 2^0, 3^1 and 5^2. which is the same as selecting 3^0, 3^1 and 5^2
Likewise, selecting 2^1, 2^3 and 5^1, is the same as selecting 2^4, 3^0 and 5^1

Does that help?

Cheers,
Brent

### "Does that help?"

"Does that help?"

Yes, I get it. Thanks. Also, if we take 3^0, 3^1 and 3^2 then the product is 27 which is not a factor of 720. ### Aha! Another reason it doesn

Aha! Another reason it doesn't work!

Cheers,
Brent

### A number N^2 has 15 factors.

A number N^2 has 15 factors. How many factors can N have?

A. 5 or 7 factors
B. 6 or 8 factors
C. 4 or 6 factors
D. 9 or 8 factors
E. 3 or 5 factors ### Great question!

Great question!

RULE: If K = (p^a)(q^b)(r^c)..., where p, q, r,...(etc.) are prime numbers, then the total number of positive divisors/factors of K is equal to (a+1)(b+1)(c+1)...

GIVEN: N² has 15 factors

Case 1: If N² = p^14 (where p is a prime number), then the total number of positive divisors/factors of N = 14+1 = 15
So, N² = p^14 satisfies the condition of having 15 factors
If N² = p^14, then N = p^7, since (p^7)² = p^14
So, if N = p^7, the RULE tells us that 7+1 = the number of positive factors of N
In other words, N can have 8 factors
ELIMINATE A, C, E

Case 2: IF N² = (p^2)(q^4) (where p and q are prime), then the total number of positive divisors/factors of N = (2+1)(4+1) = 15
So, N² = (p^2)(q^4) satisfies the condition of having 15 factors
If N² = (p^2)(q^4), then N = (p)(q^2), since [(p)(q^2)]² = (p^2)(q^4)
So, if N = (p^1)(q^2), the RULE tells us that the number of positive factors of N = (1+1)(2+1) = 6
In other words, N can have 6 factors
ELIMINATE D

Here's a similar question to practice with: https://gmatclub.com/forum/a-number-n-2-has-35-factors-how-many-factors-...

Cheers,
Brent

### Hi Brent,

Hi Brent,

Thank you for the lesson. Is there an easier way to calculate the prime factorization of 14000? (in the video you showed the factorization directly). ### Here's my lesson on Prime

Here's my lesson on Prime Factorization.

Here's how I'd probably do it.
14,000 = 14 x 1000
= 14 x 10 x 10 x 10
= 2 x 7 x 2 x 5 x 2 x 5 x 2 x 5
= 2 x 2 x 2 x 2 x 5 x 5 x 5 x 7
= (2^4)(5^3)(7)

Cheers,
Brent

### Hi Brent,

Hi Brent,

I am confused about solution for this question https://gmatclub.com/forum/if-x-and-y-are-prime-numbers-and-n-is-a-positive-integer-what-is-the-267973.html

I thought that when a statement is given to us it is a fact and we cannot question it, it is given to us that x*y=6 and that x,y are primes. Hense I thought that if we know that x*y=6 is a fact, than we can deduce that exponents are equal to 1, because if we will have higher exponents say 2^2*3^1=12, which is not equal to 6, so exponents have to be 1 and 1. What am I missing here? I think you may be incorrectly reading Statement 1 as saying (x^n)(y^n) = 6

Statement 1 actually tells us that xy = 6
Since it is given that x and y are prime, we can conclude that one value (x or y) must be 2, and the other must be 3.

Does that help?

Cheers,
Brent

### Hi Brent,

Hi Brent,

Particularly, We do know that the exponent of from the factorization above. Why we have to list out 0,1,2,3 or 4 for a; 0,1 or 2 for b and 0 or 1 for c? ### 720 = (2)(2)(2)(2)(3)(3)(5) =

720 = (2)(2)(2)(2)(3)(3)(5) = (2^4)(3^2)(5^1)

From this, we can make many conclusions such as:
(2)(2)(2)(3) is a divisor of 720
(2)(5) is a divisor of 720
(3) is a divisor of 720
(2)(3)(5) is a divisor of 720
etc.

Conversely, (2)(2)(2)(2)(2)(3) is a divisor of 720, since (2)(2)(2)(2)(2)(3) has FIVE 2's, and the prime factorization of 720 has only FOUR 2's.

For each possible divisor of 720, we can have zero, one, two, three or four 2's in the prime factorization of that divisor.
Likewise, for each possible divisor of 720, we can have zero, one, or two 3's in the prime factorization of that divisor.
And, for each possible divisor of 720, we can have zero or one 5's in the prime factorization of that divisor.

Does that help?

### Hi!

Hi!
Is there a shortcut to find the prime numbers of 1008? My calculations are too time consuming I guess.
Thanks! ### There's no specific shortcut

There's no specific shortcut one can take with prime factorization. Here's what I'd probably do:
1008 = (2)(504)
= (2)(2)(252)
= (2)(2)(2)(126)
= (2)(2)(2)(2)(63)
= (2)(2)(2)(2)(7)(9)
= (2)(2)(2)(2)(7)(3)(3)

Thanks!

### Hi Brent,

Hi Brent,

Can you solve this question - https://gmatclub.com/forum/when-the-digits-of-two-digit-positive-integer-m-are-reversed-the-res-185733.html ### Hi Brent,

Hi Brent,

Can you help solve this please? = https://gmatclub.com/forum/m01-183521.html ### And this one also please! 