Let’s start this thread from where we left the previous one on factors of a number. (If you haven’t read the Part I of this topic, we strongly suggest you read that first here )
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)
So can you deduce something here? Yes, ONLY perfect squares will have odd number of total factors and ALL perfect squares will have an odd number of total factors.
Since each of the powers is even, so each of (power + 1) is odd; their product will definitely always be odd.
How many odd factors does 100 have? 3 (An odd number)
How many even factors does 100 have? 6 (An even number)
Is this just a co-incidence? 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. So 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.
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
Total number of even factors = 21 × 4 = 84
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 us 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 more than 17 but less than 18 (because square of 17 is 289 and square of 18 is 324), so let’s assume its value to be about 17.8. If we place 17.8 among its factors, it will come after 15 but before 21 i.e. right in the middle.
1, 3, 5, 7, 9, 15, 17.8, 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.
A Quickie: 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.)
(Login required to leave a comment.)