Add Me!Close Menu Navigation

Divisors of Perfect Squares

In this article, we prove that only perfect squares have an odd number of divisors

This behavior can be readily observed in the first few natural numbers

    \[\begin{tabular}{|c|l|} \hline n & divisors \\ \hline 1 & 1 \\ 2 & 1,2 \\ 3 & 1,3 \\ 4 & 1,2,4 \\ 5 & 1,5 \\ 6 & 1,2,3,6 \\ \vdots & \\ 9 & 1,3,9 \\ \vdots & \\ 18 & 1,2,3,6,9,18\\ \vdots & \\ \hline \end{tabular}\]

Let’s start with the proposition P that

    \[\mbox{divisors}(n)\ \mbox{odd} \iff n = k^2\ |\ n,k \in \bf Z\]

Now, let’s take a slight segue and establish a method to count the number of divisors there are for any given natural n. Suppose we uniquely factor n into the product of powers of its primes n = 2^{e_2} \times 3^{e_3} \time \cdots \times p^{e_p}, then it is clear that

    \[\left(2^{e'_2} \times 3^{e'_3} \time \cdots \times p^{e'_p}\right) | \left(2^{e_2} \times 3^{e_3} \time \cdots \times p^{e_p}\right) \hspace{4mm} \mbox{whenever } e'_i \le e_i\]

We can show this by rewriting n as

    \[\left(2^{e_2} \times 3^{e_3} \time \cdots \times p^{e_p}\right) = \left(2^{e_2 - e'_2} \times 3^{e_3 - e'_3} \time \cdots \times p^{e_p - e'_p}\right) \left(2^{e'_2} \times 3^{e'_3} \time \cdots \times p^{e'_p}\right)\]

Because e_i \ge e'_i, each of e_i - e'_i \ge 0, hence \left(2^{e_2 - e'_2} \times 3^{e_3 - e'_3} \time \cdots \times p^{e_p - e'_p}\right) must still be a natural number. \blacksquare

Now let’s establish a counting argument on the divisors of n based on the powers of each of the primes in its factorization. Informally, suppose there are p prime factors of n, then in order for another number x to be a divisor of n, x must be a product of the powers of the p prime factors such that 0 \le e_i{}_x \le e_n{}_x. Suppose n = 4, there are 3 ways to fill the exponent for 2:

    \[\begin{tabular}{c|l} exponent & divisor \\ 2^0 & 1 \\ 2^1 & 2 \\ 2^2 & 4 \\ \end{tabular}\]

This suggests that in general, for each prime, there are e_n{}_p ways of filling its exponent without considering 0 and e_n{}_p + 1 ways considering 0. If there are p such exponents to be filled, then the number of total divisors is described by the expression

    \[(e_2+1)(e_3+1)\cdots(e_p+1) = \prod_{p \in \mbox{primes}} (e_p + 1)\]

Going back to the proof, the rest is trivial given the above expression.

We first consider the forward direction

    \[\mbox{divisors}(n)\ \mbox{odd} \implies n = k^2\ |\ n,k \in \bf Z\]

If \prod_{p \in \mbox{primes}} (e_p + 1) is odd, then it must be the case that all (e_p + 1) \mbox{ odd} \iff e_p \mbox{ even}. If all exponents of the primes are even, then naturally n is a perfect square. \blacksquare

Next, we consider the reverse direction

    \[n = k^2 \implies \mbox{divisors}(n)\ \mbox{odd}\ |\ n,k \in \bf Z\]

If n = k^2 and k = \left(2^{e_2} \times 3^{e_3} \time \cdots \times p^{e_p}\right), then n = \left(2^{2e_2} \times 3^{2e_3} \time \cdots \times p^{2e_p}\right). Therefore, the number of divisors of n is

    \[\prod_{p \in \mbox{primes}} (2e_k{}_p + 1)\]

Because 2x + 1 will always be odd, the product of a finite number of odd natural numbers will still be odd, hence \mbox{divisors}(n) is odd whenever n is a perfect square. \blacksquare

Posted By Lee

Woosh

Recent Comments