On this page
List the factors of most whole numbers and you get an even count. The exceptions are 1, 4, 9, 16, 25 and every other perfect square. The reason takes one line, and it also solves a locker puzzle from Class 8 NCERT maths.
Why do factors come in pairs?
Every factor d of a number n has a partner, n ÷ d, and the two multiply back to n. Take 12: its factors pair up as 1 × 12, 2 × 6 and 3 × 4, so 12 has 6 factors. In each pair of two different factors, one is smaller than √n and the other is larger, which is why you only ever need to search up to the square root.
For a non-square n, every factor d is paired with a different factor n/d, so the number of factors is even, as the Wikipedia article on the divisor function sets out.
Why do perfect squares have an odd number of factors?
Now try 36. The pairs are 1 × 36, 2 × 18, 3 × 12, 4 × 9 and 6 × 6. The last pair is one number used twice, and you count 6 only once. So 36 has four true pairs plus one lone factor: 1, 2, 3, 4, 6, 9, 12, 18, 36. That is 9 factors.
A whole number has an odd number of factors exactly when it is a perfect square; the OEIS entry for the divisor-counting sequence A000005 states it as "a(n) is odd iff n is a square".
If n is not a square, no factor can be its own partner, because d = n/d would mean d² = n, so the count is even. If n is a square, exactly one factor, √n, is its own partner, so the count is odd.
Does the prime factorisation formula agree?
It does, and it gives you a second proof. If n = p^a × q^b × ..., the number of factors is (a + 1)(b + 1)..., the formula given in the same divisor function article. Our guide to the number of divisors and their sum by prime factorisation works through the method step by step.
A product is odd only if every bracket is odd, and (a + 1) is odd only when a is even. A number whose prime powers are all even is a perfect square. Check it:
72 = 2³ × 3², so it has 4 × 3 = 12 factors: even, and 72 is not a square.
144 = 2⁴ × 3², so it has 5 × 3 = 15 factors: odd, and 144 = 12².
Which lockers stay open in the 100-locker puzzle?
The puzzle is Queen Ratnamanjuri's game from the chapter A Square and a Cube in the Class 8 NCERT book Ganita Prakash, as this chapter walkthrough shows. There are 100 lockers, all closed, and 100 people numbered 1 to 100. Person 1 opens every locker, person 2 changes the state of every second locker, person 3 every third, and so on. Which lockers are open at the end?
Person k touches locker n only if k is a factor of n, so locker n is toggled once for each of its factors. It starts closed, so it ends open only after an odd number of toggles: only when n is a perfect square.
Locker 48 has factors 1, 2, 3, 4, 6, 8, 12, 16, 24, 48: 10 toggles, so it ends closed.
Locker 49 has factors 1, 7, 49: 3 toggles, so it ends open.
The open lockers are 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100: ten of them, because 10² = 100.
Between 81 and 100 there are 18 closed lockers, 82 to 99, which matches the pattern in our post on why there are 2n non-square numbers between n² and (n + 1)².
How do you use this in an exam question?
Every twist comes back to one rule, set out in the ProofWiki write-up of the locker problem: a locker that starts closed ends open only if it is toggled an odd number of times.
How many lockers are open? Count the squares up to N: the answer is the largest whole number whose square is at most N. For 1,000 lockers it is 31, since 31² = 961 and 32² = 1,024.
Which lockers were touched exactly 3 times? A number has exactly 3 factors only if it is the square of a prime, p², with factors 1, p and p². Up to 100 that is 4, 9, 25 and 49.
What if every locker started open? Flip the answer. The 10 square lockers end closed and the other 90 end open.
If a variant still trips you up, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. To rebuild the idea from scratch, try the lessons in the Fermi Concept Library.
For another proof this short, read Euclid's proof that there are infinitely many primes.
