Question

This topic has expert replies
User avatar
Legendary Member
Posts: 866
Joined: Mon Aug 02, 2010 6:46 pm
Location: Gwalior, India
Thanked: 31 times

Question

by goyalsau » Sun Nov 07, 2010 10:24 pm
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...
Saurabh Goyal
[email protected]
-------------------------


EveryBody Wants to Win But Nobody wants to prepare for Win.

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2621
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Mon Nov 08, 2010 12:24 am
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 ..
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:

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

User avatar
Legendary Member
Posts: 866
Joined: Mon Aug 02, 2010 6:46 pm
Location: Gwalior, India
Thanked: 31 times

by goyalsau » Mon Nov 08, 2010 3:38 am
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,
Saurabh Goyal
[email protected]
-------------------------


EveryBody Wants to Win But Nobody wants to prepare for Win.

User avatar
Legendary Member
Posts: 866
Joined: Mon Aug 02, 2010 6:46 pm
Location: Gwalior, India
Thanked: 31 times

by goyalsau » Tue Nov 09, 2010 3:13 am
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
Saurabh Goyal
[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

by beat_gmat_09 » Tue Nov 09, 2010 4:23 am
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...
This is a proved one. I am just putting the stmt with one example.

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

User avatar
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

by MAAJ » Tue Nov 09, 2010 10:32 am
Ian Stewart wrote:
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 ..
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:

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.
Very nice post!!!! Thank you!!!! you detailed it very well :)