0
$\begingroup$

Prove $\sigma$(n) $\equiv$ $d(n)$ mod 2 where $\sigma(n)$ is the divisor function and $d(n)$ is the number of divisors of n. So, this is equivalent to saying that $\frac{\sigma(n)}{d(n)}$ $\equiv$ 1 mod 2. So I just have to show that the fraction of $\sigma(n)$ and $d(n)$ is odd. We know that $\sigma(n) = \prod\sigma(p^{a_{i}}_{i})$ for each $p^{a_{i}}_{i}$ in the prime factorization on n. I also know that $d(n) = \prod(a_i + 1)$ for each $a_i$ in the prime factorization of n. So this will yield $\prod\frac{\sigma(p^{a_{i}}_{i})}{a_i + 1}$. I'm not quite sure how I'm able to simplify this further or manipulate it.

$\endgroup$
1
$\begingroup$

If I understand your proposed theorem correctly, it is not true. I am assuming you mean the sum of divisors function by $σ(n)$. As a counterexample, $σ(2)=3$ and $d(2)=2$. However, your theorem is true for $n$ with an even number of 2 factors, or, in other words, for odd $n$ or $n$ divisible by 4. In fact, your proposed theorem is false in all other cases ($n$ divisible by $2$ but not by $4$).

I don't see any motivation for the fraction approach. I would just write this out explicitly.

Let $n$ = $2^mp_1^{e_1}*\cdots*p_k^{e_k}$. Then $$σ(n)=(1+2+\cdots+2^m)(1+p_1+\cdots+p_1^{e_1})*\cdots*(1+p_k+\cdots+p_k^{e_k})$$ This has $(e_1+1)*\cdots*(e_k+1)$ odd terms, which is precisely the number of odd divisors of $n$. If $m$ is even, then the total number of divisors of $n$ is an odd multiple of the number of odd divisors. Thus, for odd $m$, $σ(n)$ is odd iff $d(n)$ is odd.

$\endgroup$

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.