Prove: If the sum of all positive divisors of $ n \in \mathbb{Z}^{+}$ is a power of two, then the number/amount of the divisors is a power of two.
Problem
Source: MEMO 2008, Team, Problem 8
Tags: number theory unsolved, number theory
sumita
11.09.2008 01:34
lemma:if $ (a^n-1)=2^k(a-1)$ then $ n$ is a power of two. suppose the inverse so exist odd prime $ p$ that$ p|n$ so $ (a^p-1)|(a^n-1)=2^k(a-1)$ so $ a^{p-1}+....+a +1$ is power of two .hence p is odd its impossible.so n is a power of two. we now that if $ n=\prod p_{i}^{\alpha_{i}}$ then the sum of divisor of n is $ \prod (p_{i}^{\alpha_{i}}+...+p+1)$ because of lemma we have $ \alpha_{i}+1$ is power of two.so the number of divisor is power of two.
me@home
04.08.2010 06:27
Decompose $n: \ \prod_i p_i^{e_i}$; then $\sigma(n) = \prod_i\left(\sum_{j=0}^{e_i} p_i^{j}\right)$
Immediately, we see that $p_i\not=2$, hence each $p_i$ is odd $(1)$.
Also, it is clear that \[\sigma(n) = 2^k \implies \sum_{j=0}^{e_i} p_i^{j}=2^{k_i}\]
Now $e_i+1$ is a power of two; indeedsuppose for contradiction that it wasn't. Then pick an odd prime $q|e_i+1$:
\[2^{k_i}=\sum_{j=0}^{e_i} p_i^{j}=\left(\sum_{j=0}^{q-1} p_i^{j}\right)\left(\sum_{j=0}^{\frac{e_i+1}{q}-1} p_i^{qj}\right)\]
However, this yields a contradiction, since the quantity $\left(\sum_{j=0}^{q-1} p_i^{j}\right)$ is the sum of an odd number of odd terms (by $(1)$), and hence clearly odd.
Lastly, it is clear to see from above (and well-known) that the \[\text{number of divisors } = \prod_i (e_i+1)\]
which must be a power of two, since each $e_i+1$ is a power of two.