HI! Guys,
I want to know about factorization, We all know how to factor any particular number. But.......
Lets take an example of 3600.
total number of factors of 3600 = 2^4 , 3^2 , 5^2,
that will equal to 5 * 3 * 3 = 45 { we know this very well }
we add 1 to every power because we considers powers from 0 to 4,
Like 2^0 , 2^1 , 2^2 , 2^3, 2^4 ... in all { 5 }
same with 3 and 5,
I want to know why we do it like this, why we multiply 5 * 3 * 3 ..
I am asking because i a question it was asked how many divisors of 3600
1. divisors of 10
2. divisors of 12
3. odd divisors
4. even divisors.
5. end with 5
and so on and so for........
I want to the principle why we do it like this, i searched it on google but still not convinced with the answer if you guys can share why it is like this, '
Than it will be great...
Question
This topic has expert replies
- goyalsau
- Legendary Member
- Posts: 866
- Joined: Mon Aug 02, 2010 6:46 pm
- Location: Gwalior, India
- Thanked: 31 times
Saurabh Goyal
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
Good question, and you've almost answered it yourself. Let's use the number 3600 = (2^4)(3^2)(5^2) as an example. What would a divisor of this number look like? It must look like (2^a)(3^b)(5^c), where:goyalsau wrote:HI! Guys,
I want to know about factorization, We all know how to factor any particular number. But.......
Lets take an example of 3600.
total number of factors of 3600 = 2^4 , 3^2 , 5^2,
that will equal to 5 * 3 * 3 = 45 { we know this very well }
we add 1 to every power because we considers powers from 0 to 4,
Like 2^0 , 2^1 , 2^2 , 2^3, 2^4 ... in all { 5 }
same with 3 and 5,
I want to know why we do it like this, why we multiply 5 * 3 * 3 ..
a can be 0, 1, 2, 3 or 4
b can be 0, 1 or 2
c can be 0, 1 or 2
So if we want to 'invent' a divisor of 3600, we have 5 choices for a, 3 choices for b, and 3 choices for c. Now to count the number of divisors we can make, this is just a standard counting problem: we multiply our choices for each letter, so we have 5*3*3 = 45 divisors in total.
If you understand this, you should be able to modify this method if you're given certain restrictions on the type of divisors you wish to count. So, for example, if we want to know how many even divisors there are of (2^4)(3^2)(5^2), again, our divisors must look like (2^a)(3^b)(5^c), but if our divisor is even, a *cannot* be zero; an even divisor must contain at least one 2. So we only have 4 choices for a, but we still have 3 choices for each of b and c, and we have 4*3*3 = 36 even divisors in total. Conversely, if we want to count odd divisors, then a *must* be 0, so we only have 1 choice for a, and 1*3*3 = 9 odd divisors in total. This should make sense, since when we add the number of even divisors and the number of odd divisors, we must get 45, the total number of divisors.
You might now want to try the other questions you've asked as practice. You can answer each of them if you just think about what values a, b and c are allowed to have.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com
ianstewartgmat.com
ianstewartgmat.com
- goyalsau
- Legendary Member
- Posts: 866
- Joined: Mon Aug 02, 2010 6:46 pm
- Location: Gwalior, India
- Thanked: 31 times
Thanks Ian , Thanks a lot,
I just need a little more help,
I want to know why we multiply ?
Multiples of 3600 which are divisors of 10 as well.
In that case 2^0 is not possible, and 5^0 is also not allowed.
so we left with,
4 values of 2
3 values of 3
2 values of 5
in all 4 * 3 * 2 = 24, { why in this case only values of 3 and 5, will not be formed }
divisors of 12
now 2^0 and 2 ^1 will not be allowed, and 3^0, will not be allowed as well.
3 values of 2
2 values of 3
3 values of 5
3 * 2 * 3 = 18
I want to know while considering the factors of 3600 which are divisible by 12, we want at least 2^2, and 3^1.
and we are also considering 3 factors of 5 as well.
I need to know how this counting principle works,
Because i was thinking what if we take only 3 values of 5 and 2 values of 3,
in that case the number will not be divisible by 12,
I just need a little more help,
I want to know why we multiply ?
Multiples of 3600 which are divisors of 10 as well.
In that case 2^0 is not possible, and 5^0 is also not allowed.
so we left with,
4 values of 2
3 values of 3
2 values of 5
in all 4 * 3 * 2 = 24, { why in this case only values of 3 and 5, will not be formed }
divisors of 12
now 2^0 and 2 ^1 will not be allowed, and 3^0, will not be allowed as well.
3 values of 2
2 values of 3
3 values of 5
3 * 2 * 3 = 18
I want to know while considering the factors of 3600 which are divisible by 12, we want at least 2^2, and 3^1.
and we are also considering 3 factors of 5 as well.
I need to know how this counting principle works,
Because i was thinking what if we take only 3 values of 5 and 2 values of 3,
in that case the number will not be divisible by 12,
Saurabh Goyal
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
- goyalsau
- Legendary Member
- Posts: 866
- Joined: Mon Aug 02, 2010 6:46 pm
- Location: Gwalior, India
- Thanked: 31 times
I am explaining with a smaller value say 12.
Now 12 = 2^2 * 3^1.
Actually count the factors of 12 which are 1, 2, 3, 4, 6, 12.
Now 1 = 2^0 * 3^0.
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0.
6 = 2^1* 3^1
12 = 2^2 * 3^1.
See the pairing of powers of 2 and 3.
They are (0,0), (1, 0), (0, 1), (2, 0), (1, 1), (2, 1).
Rearranging we get (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1).
So we see that we can get the above by multiplying the two columns
0 0
1 1
2
If we multiply each element of first column by each element of second column, we get the required pairs.
So the number of pairs will be (number of elements in first column) * (number of elements in second column) = 3* 2 = 6.
This also gives the number of factors of 12 = 6.
Hope this part is clear as to why we multiply.
If any doubt still exists, please ask again.
Rahul Thanks a lot for the above explanation,
like we did it two factors 2 and 3.
How we will do it when we will have three factors
2 , 3 and 5
Now 12 = 2^2 * 3^1.
Actually count the factors of 12 which are 1, 2, 3, 4, 6, 12.
Now 1 = 2^0 * 3^0.
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0.
6 = 2^1* 3^1
12 = 2^2 * 3^1.
See the pairing of powers of 2 and 3.
They are (0,0), (1, 0), (0, 1), (2, 0), (1, 1), (2, 1).
Rearranging we get (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1).
So we see that we can get the above by multiplying the two columns
0 0
1 1
2
If we multiply each element of first column by each element of second column, we get the required pairs.
So the number of pairs will be (number of elements in first column) * (number of elements in second column) = 3* 2 = 6.
This also gives the number of factors of 12 = 6.
Hope this part is clear as to why we multiply.
If any doubt still exists, please ask again.
Rahul Thanks a lot for the above explanation,
like we did it two factors 2 and 3.
How we will do it when we will have three factors
2 , 3 and 5
Saurabh Goyal
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
[email protected]
-------------------------
EveryBody Wants to Win But Nobody wants to prepare for Win.
-
- Master | Next Rank: 500 Posts
- Posts: 437
- Joined: Sat Nov 22, 2008 5:06 am
- Location: India
- Thanked: 50 times
- Followed by:1 members
- GMAT Score:580
This is a proved one. I am just putting the stmt with one example.goyalsau wrote:HI! Guys,
I want to know about factorization, We all know how to factor any particular number. But.......
Lets take an example of 3600.
total number of factors of 3600 = 2^4 , 3^2 , 5^2,
that will equal to 5 * 3 * 3 = 45 { we know this very well }
we add 1 to every power because we considers powers from 0 to 4,
Like 2^0 , 2^1 , 2^2 , 2^3, 2^4 ... in all { 5 }
same with 3 and 5,
I want to know why we do it like this, why we multiply 5 * 3 * 3 ..
I am asking because i a question it was asked how many divisors of 3600
1. divisors of 10
2. divisors of 12
3. odd divisors
4. even divisors.
5. end with 5
and so on and so for........
I want to the principle why we do it like this, i searched it on google but still not convinced with the answer if you guys can share why it is like this, '
Than it will be great...
When objects are not all distinct the number of ways to select one or more objects from them is equal to (q1+1)(q2+2)(q3+1)(q4+1)....(qt+1) - 1. Where there are q1 of the first kind, q2 of the second kind... and qt of the t'th kind.
Example - How many divisors does the number 1400 have ?
1400 = 2^3 X 5^2 X 7^1
Now q1=3, q2=2, q3=1. The number of ways of selecting is (3+1) X (2+1) X (1+1) -1 = 23.
Here we also have to consider 1 as the factor (i.e if nothing is selected then 1 is the factor), therefore the number of factors are 23+1=24. Origin is from the aforementioned combinations formula. This combinations formula can also be used for solving other problems.
Hence, number of ways of selecting 0 or more objects is - (q3+1)(q4+1)....(qt+1)
which is used for getting the number of factors.
Hope is the dream of a man awake
- MAAJ
- Master | Next Rank: 500 Posts
- Posts: 243
- Joined: Sun Jul 12, 2009 7:12 am
- Location: Dominican Republic
- Thanked: 31 times
- Followed by:2 members
- GMAT Score:480
Very nice post!!!! Thank you!!!! you detailed it very wellIan Stewart wrote:Good question, and you've almost answered it yourself. Let's use the number 3600 = (2^4)(3^2)(5^2) as an example. What would a divisor of this number look like? It must look like (2^a)(3^b)(5^c), where:goyalsau wrote:HI! Guys,
I want to know about factorization, We all know how to factor any particular number. But.......
Lets take an example of 3600.
total number of factors of 3600 = 2^4 , 3^2 , 5^2,
that will equal to 5 * 3 * 3 = 45 { we know this very well }
we add 1 to every power because we considers powers from 0 to 4,
Like 2^0 , 2^1 , 2^2 , 2^3, 2^4 ... in all { 5 }
same with 3 and 5,
I want to know why we do it like this, why we multiply 5 * 3 * 3 ..
a can be 0, 1, 2, 3 or 4
b can be 0, 1 or 2
c can be 0, 1 or 2
So if we want to 'invent' a divisor of 3600, we have 5 choices for a, 3 choices for b, and 3 choices for c. Now to count the number of divisors we can make, this is just a standard counting problem: we multiply our choices for each letter, so we have 5*3*3 = 45 divisors in total.
If you understand this, you should be able to modify this method if you're given certain restrictions on the type of divisors you wish to count. So, for example, if we want to know how many even divisors there are of (2^4)(3^2)(5^2), again, our divisors must look like (2^a)(3^b)(5^c), but if our divisor is even, a *cannot* be zero; an even divisor must contain at least one 2. So we only have 4 choices for a, but we still have 3 choices for each of b and c, and we have 4*3*3 = 36 even divisors in total. Conversely, if we want to count odd divisors, then a *must* be 0, so we only have 1 choice for a, and 1*3*3 = 9 odd divisors in total. This should make sense, since when we add the number of even divisors and the number of odd divisors, we must get 45, the total number of divisors.
You might now want to try the other questions you've asked as practice. You can answer each of them if you just think about what values a, b and c are allowed to have.
![Smile :)](./images/smilies/smile.png)