15
$\begingroup$

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it.

For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ has odd # of positive divisors.

$\Rightarrow$: If $n$ is a perfect square it must consist of 1+ prime factors each to an even power. If $n$ consists of 1+ prime factors each to an even power it must have an odd # of positive divisors because each even power contributes itself plus $1$(for the $0$ case) to the number of divisors for product $n$.

$\Leftarrow$: If $n$ has an odd number of positive divisors it must consist of 1+ prime factors each to an even power. If $n$ consists of 1+ prime factors each to an even power it must be a perfect square.

Thanks.

$\endgroup$
1
  • $\begingroup$ Your first implication is good, although you should say why (all prime factors have an even power) implies (odd number of positive divisors). Your second implication, in particular the first sentence, is very much not obvious and needs explanation. $\endgroup$ Aug 22, 2014 at 20:46

4 Answers 4

29
$\begingroup$

HINT: Write $n = p_1^{a_1} \dots p_k^{a_k}$, where $p_1, \dots, p_k$ are distinct primes. Then the number of positive divisors of $n$ is given by $(a_1 +1)(a_2 + 1)\dots(a_k+1)$. In order for this number to be odd, each of the terms $a_i + 1$ must also be odd. What does this tell us about each $a_i$?

$\endgroup$
2
  • 1
    $\begingroup$ Yeah that's basically what I said, just more briefly, IMO. $\endgroup$
    – miniparser
    Aug 22, 2014 at 16:52
  • 2
    $\begingroup$ You've argued in one direction ($n$ a perfect square implies the number of positive divisors is odd), but you can use this hint to argue in the other direction (number of positive divisors is odd implies $n$ is a perfect square) $\endgroup$
    – Nick
    Aug 22, 2014 at 16:54
15
$\begingroup$

If $a$ and $b$ are distinct positive integers such that $ab=n$, call the pair $\{a,b\}$ a couple, or in the business-oriented language of today, partners. Call a positive divisor $a$ of $n$ self-sufficient if $a$ does not have a partner. Note that $a$ is self-sufficient if and only if $\frac{n}{a}=a$, that is, if and only if $n$ is a perfect square and $a$ is its square root.

If $n$ is not a perfect square, the set of positive divisors of $n$ is made up of a number, possibly $0$, of couples, so the number of divisors of $n$ is even.

If $n$ is a perfect square, then the set of of positive divisors of $n$ is made up of a number of couples, together with a self-sufficient number, so the number of positive divisors is odd.

$\endgroup$
1
$\begingroup$

If two integers multiply to equal N, you will add two divisors to your total for that number. This will be true for all values except when the two integers are the same. Divisors will always be added in pairs except in this case. So the only way to get to an odd total, is when the two divisors are equal, or N is a perfect square.

$\endgroup$
0
$\begingroup$

Your forward direction looks good. The accepted answer does a good job using the conventional notation for the sum of positive divisors, $\nu(n)$. Here's the reverse direction.

Let $n$ be some square. Now, $n^2=n\cdot n=(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_l^{\alpha_l})\cdot(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_l^{\alpha_l})=p_1^{2\alpha_1}p_2^{2\alpha_2}\cdots p_l^{2\alpha_l}$. It is clear the exponents (meaning the $2\alpha_i$'s) of the prime factorization must be even. Thus, $\nu(n^2)=(2\alpha_1+1)(2\alpha_2+1)\cdots(2\alpha_l+1)$. Evidently each term of $\nu(n^2)$ must be odd, which means their product will be odd, i.e., $\nu(n^2)$ is odd.

A worked example is $\nu(196)$: $196=14\cdot14=(2^1\cdot7^1)\cdot(2^1\cdot7^1)=2^{2(1)}\cdot7^{2(1)}=2^2\cdot7^2$. $\nu(196)=\nu(14^2)=(2+1)(2+1)=9$. Evidently $196$ has $9$ positive divisors: $1, 2, 4, 7, 14, 28, 49, 98, 196$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy