Let’s start this thread from where we left the previous one. (If you haven’t read my previous post on this topic, I strongly suggest you read it first: Writing Factors of an Ugly Number.)

What happens if the total number of factors of a number is odd?

Let us take the example of N = 100. Break it down into its prime factors.

100 = 10 × 10 = 2^^{2} × 5^^{2}

How many factors will it have? (2 + 1)(2 + 1) = 9. Let us write them down:

1, 2, 4, 5, 10, 20, 25, 50, 100

1 × 100 = 100; 2 × 50 = 100; 4 × 25 = 100; 5 × 20 = 100.

10 is in the middle. It has no companion with which it could multiply and give 100! But, 10 will multiply with itself to give 100 (10 × 10 = 100). This means, we have a factor which multiplies by itself to give the number. Hence the number N (=100 here) must be a perfect square!

**ONLY perfect squares will have odd number of total factors and ALL perfect squares will have an odd number of total factors.**

Referring back to the formula of total factors, since each of the powers is even, so each of (power + 1) is odd; their product will definitely always be odd.

A short Q&A session here:

Q: How many odd factors does 100 have?

A: 3 (1, 5 and 25 – An odd number)

Q: How many even factors does 100 have?

A: 6 (2, 4, 10, 20, 50, 100 – An even number)

Q: Is this just a co-incidence?

A: No. Let me explain:

100 = 2^^{2} × 5^^{2}

If we want to find out its odd factors, we need to find how many factors we can make out of 5^{^2}. (We need to drop the 2s since 2s create even factors.). We can make only (2 + 1) = 3 odd factors. Since power of 5 is even, (power + 1) will be odd. **A perfect square always has odd number of odd factors.**

If we want to find out its even factors, we multiply each of the odd factors by 2 or 2^{2}. We can take 2 in two ways (one 2 or two 2s). We cannot take no 2 because that just leaves us with an odd factor. So we get 3 × 2 = 6 even factors. **A perfect square always has even number of even factors.**

What happens when we add all these factors together? Adding the odd number of factors (3) with the even number of factors (6) will give us an odd number of total factors (9). This will be true for all perfect squares.

Let’s look at another example.

N = 2^^{4} × 7^^{2} × 11^^{6}

This is a perfect square because powers of all prime factors are even.

Total number of factors = (4 + 1)(2 + 1)(6 + 1) = 105

Total number of odd factors = (2 + 1)(6 + 1) = 21 (Dropped the 2)

Total number of even factors = 21 × 4 = 84 (Each odd factor multiplied by 2/2^2/2^3/2^4)

Or if you like, we can say out of a total of (4 + 1)(2 + 1)(6 + 1) factors, 4(2 + 1)(6 + 1) are even (since they have a 2) and 1(2 + 1)(6 + 1) are odd since they do not have a 2.

Sum of the 21 odd factors will be odd and sum of the 84 even factors will be even. Hence, sum of all the factors will be odd.

Note: **The sum of all factors of a perfect square is always odd but if the sum of all factors of a number is odd, we cannot say that it must be a perfect square.** E.g. 18 has 6 factors (1, 2, 3, 6, 9, 18). Their sum is 39, an odd number but 18 is not a perfect square.

A Great Little Application: If we want to find whether 91 is a prime number, can the logic of factors help us? (It must since it is a part of the ‘Factors’ post.)

A number is prime when it has no factors other than 1 and itself. So if we want to find out whether 91 is prime, we need to find if it has any other factors. I can’t think of what to break it down into so my first impulse is to say that it is prime. But let me check to be sure that we are not missing anything. 91 is not divisible by 2, not by 3 either, not by 5, but it is divisible by 7! So it is not prime.

What about 83?

Let me check – not divisible by 2, not by 3, not by 5, not by 7, not by 11…. How long do we need to go? Do we need to check for all prime numbers till 83? No! Because we saw above that factors occur in pairs. If a big number is a factor of 83, there will be a corresponding small number which will also be a factor of 83. If we couldn’t find any factor of 83 in the small numbers, we wouldn’t find any in the big numbers too… Now, ‘small’ and ‘big’ are arbitrary terms. We want to know exactly till what number should we check. Do you remember which number was exactly in the middle of the factors? Yes, the square root! Even if the square root isn’t a factor like in case of 315, if we do place it among the factors, it will be in the middle. E.g. square root of 315 is around 17.7 (because square of 17 is 289 and square of 18 is 324. If we place 17.7 among its factors, it will come after 15 but before 21 i.e. right in the middle.

1, 3, 5, 7, 9, 15, 17.7, 21, 35, 45, 63, 105, 315

So we should check till the square root of the number.

Since square root of 83 is a little more than 9, we should check for all prime numbers less than 9. If there isn’t any factor in those, there wouldn’t be any factor in the numbers greater than 9.

Quick Question: Is 103 prime?

Not divisible by 2, not by 3, not by 5, not by 7… that’s it. It is prime.

(Square root of 103 is a little more than 10 so we only need to check for primes less than 10.)

*Karishma, a Computer Engineer and GMAT prep instructor with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep in Detroit, Michigan, and regularly participates in content development projects such as this blog!*

## Quarter Wit, Quarter Wisdom: Factors of Perfect Squares

*Posted on December 13, 2010, filed in: GMAT, Quarter Wit, Quarter Wisdom*

Just picked up on this little nugget of gold(is xyz a prime)…one of those low-hanging fruit that works in a pinch.

Excellent Krishna!.

Karishma,

I can vouch for – you are at least one of the best minds in GMAT math.

The tip on how to check the prime number is really helpful. Thank you Karishma.

You could also check if a number is prime by dividing it by 6 and if the remainder is either a 1 or 5, then it is a prime. It works for most of the times but there are also numbers that leave a remainder 1 or 5 which aren’t prime. It is based on the concept that all primes are in the form 6k+1 or 6k-1 but also numbers in the same form aren’t always prime.

Exactly! That is the reason you cannot use this property of prime numbers to check whether a number is prime. Not all numbers of the form (6n+1) or (6n-1) are prime.

Great tips Krishna. You will definitely help a lot of people to improve their score with this. Thanks.