# A conjecture concerning the number of divisors and the sum of divisors.

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$.

• Thank you for your answer! I will go in detail through your proof and accept the answer if I understand everything. – orgesleka May 3 '18 at 13:44
• I think there might be a factor of $2^{2k_1}$ missing in the last display equation. It still supports the conclusion. – David K May 3 '18 at 13:47
• +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 – Henry May 3 '18 at 13:51
• Thanks, David K! The last product must begin by $i=1$. Henry's Summary is also good. – 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.