I stumbled upon the following conjecture:

Let $n$ be a positive integer. Let $\sigma\left(n\right)$ be the sum of all (positive) divisors of $n$, and let $\tau\left(n\right)$ be the number of these divisors. Then, $$\tau(n)+\sigma(n)\equiv 1 \mod 2 \iff n = 2m^2 \text{ for some integer } m .$$

Does anybody have an idea on how to prove this, maybe in parts? Or maybe someone has a counterexample?


In fact, this conjecture holds as we will show.

Proof: Let $n = \prod_{i=1}^n p_i^{e_i}$, then $$\tau(n) = \prod_{i=1}^n (e_i +1)$$ and $$\sigma(n) = \prod_{i=1}^n \Big( \sum_{j=0}^{e_i} p_i^j \Big).$$ For $p_i >2$, we see that $(e_i +1)$ is even if and only if $ \sum_{j=0}^{e_i} p_i^j$ is even (sum of $n$ odd numbers is even if and only if $n$ is even). In other words $$(e_i+1) \equiv \sum_{j=0}^{e_i} p_i^j \quad \mathrm{mod} \ 2.$$ Thus, if only one $e_i$ of the $p_i >2$ is odd, we get already that $$\tau(n) + \sigma(n) \equiv 0 \quad \mathrm{mod} \, 2.$$ Assuming that $$\tag{1} \tau(n) + \sigma(n) \equiv 1 \quad \mathrm{mod} \ 2$$ we see that all $e_i$ are even if $p_i >2$. If $p_1=2$, then (1) reduces to $$(e_1+1) + 2^{e_1+1} -1 \equiv 1 \quad \mathrm{mod} \ 2.$$ Thus $e_1 \equiv 1 \mod 2$. Writing $e_1 = 2 k_1 +1 $ and $e_i = 2k_i$, we get $$n = 2 m^2,$$ where $$m = \prod_{i=1}^n p_i^{k_i}.$$ This calulcations shows also that for $n = 2m^2$ we have $\tau(n)+\sigma(n) \equiv 1 \ \mathrm{mod} \ 2$.

  • $\begingroup$ Thank you for your answer! I will go in detail through your proof and accept the answer if I understand everything. $\endgroup$ – orgesleka May 3 '18 at 13:44
  • 1
    $\begingroup$ I think there might be a factor of $2^{2k_1}$ missing in the last display equation. It still supports the conclusion. $\endgroup$ – David K May 3 '18 at 13:47
  • 3
    $\begingroup$ +1: As a summary, the number of divisors $\tau(n)$ is odd iff $n$ is a square, while the sum of divisors $\sigma(n)$ is odd iff $n$ is a square or twice a square, so $\tau(n)+\sigma(n)$ is odd iff $n$ is twice a square $\endgroup$ – Henry May 3 '18 at 13:51
  • $\begingroup$ Thanks, David K! The last product must begin by $i=1$. Henry's Summary is also good. $\endgroup$ – p4sch May 3 '18 at 15:03

In a more descriptive style of argument:

The parity of $\tau(n)$, the number of divisors of $n$, depends on whether the divisors are composed entirely of distinct factor pairs $(d_1,d_2)$ or whether there is a square root $n=d_s\cdot d_s$ to make the count odd.
$\tau(n)$ is odd $\iff n$ is a perfect square.

The parity of $\sigma(n)$, the sum of divisors of $n$, depends on the count of its odd factors. We can thus ignore all even factors of $n$, so focus on the odd number $\ell$ defined by $n=2^k\ell$. Then as before if $\ell$ has only distinct factor pairs $(d_1,d_2)$ the sum will be even, and only if $\ell$ has a square root $d_s$ will the sum be odd.
$\sigma(n)$ is odd $\iff \ell$, the largest odd factor of $n$, is a perfect square.

So for $\tau(n)+\sigma(n)$ to be odd, we cannot have $n$ a perfect square - that would make both $\tau(n)$ and $\sigma(n)$ odd, so the sum even. So we need $\ell$ square (for $\sigma(n)$ odd) and $2^k$ not square (for $\tau(n)$ even), which makes $2^{k-1}$ square. Thus we can set $m=\sqrt{2^{k-1}\ell\ \ }$ giving $n=2m^2$.

By the same calculations we can see that $n=2m^2$ will give $\tau(n)+\sigma(n)$ odd.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.