shashank.ism wrote:
Harsh will you please explain how can we come to conclusion that only perfect squares have odd number of factors..
well if its true, it is really a nice concept and can be used to solve a problem in small time. Thanks for this question.
It is indeed true that only perfect squares have an odd number of factors. There are two ways to see this:
* Notice that most of the time, factors come in pairs. If, for example, we look at the number 26, we have four factors -- that is, two pairs of numbers that multiply to 26:
1 * 26 = 26
2 * 13 = 26
* It is only for a perfect square that we have one factor, the positive square root of the number, which is not in a pair. Look at, say, 16, which has five factors:
1 * 16 = 16
2 * 8 = 16
4^2 = 16
__
Alternatively, if you know how we count divisors from a prime factorization, you can see that perfect squares will have an odd number of factors. If we have a prime factorization, we count divisors by adding one to each exponent and multiplying. So the number (2^7)(3^5), for example, has 8*6 = 48 positive factors.
Now, if a number is a perfect square, all of the exponents in its prime factorization must be even. For example, the prime factorization of 144 = 12^2 = (2^2 * 3)^2 is (2^4)(3^2). So when we add one to each power, we will get only odd numbers: 5*3 = 15, and 144 has fifteen positive divisors. If, on the other hand, any of our exponents are odd numbers, when we add one we will get an even number, and therefore an even number of divisors, so if a number is *not* a perfect square, it must have an even number of factors.
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
