Let $n$ be a positive integer such that the sum of all its positive divisors (inclusive of $n$) equals to $2n + 1$. Prove that $n$ is an odd perfect square. related: https://artofproblemsolving.com/community/c6h515011 https://artofproblemsolving.com/community/c6h108341 (Putnam 1976) https://artofproblemsolving.com/community/c6h368488 https://artofproblemsolving.com/community/c6h445330 https://artofproblemsolving.com/community/c6h378928
Problem
Source: 2006 singapore NTST
Tags: number theory
30.03.2018 20:53
03.10.2019 05:24
As above noticed, $n$ can be written in the form $2^k \cdot m^2$ for a non-negative integer $k$ and odd integer $m.$ Lemma 1. $k$ is even. Proof. Assume not, for contradiction. Then notice that $\sigma(2^k)|\sigma(n)$ implies that $3|\sigma(n)$, because $\sigma(2^k) \equiv 0$ (mod $3$) for odd $k.$ This means that $n \equiv 1$ (mod $3$). Since $2^k \equiv 2$ (mod $3$) if $k$ is odd, we'd then have $m^2 \equiv 2$ (mod $3$). That's absurd. $\blacksquare$ Hence, we can let $k = 2 \ell$ for some nonnegative integer $\ell.$ Suppose, for contradiction, that $\ell > 0.$ Then, observe that $\sigma(2^{2\ell}) \equiv 7$ (mod $8$), and so therefore there exists a prime $p|\sigma(2^{2\ell})$ which is not $1, 3$ (mod $8$). But then notice that $p| \sigma(n) = 2n+1.$ Since $n$ is a square, we then know that $2x^2 + 1 \equiv 0$ (mod $p$) for some $x \in \mathbb{N}.$ However, $\frac{-1}{2}$ is not a quadratic residue modulo $p$ if $p \not \equiv 1, 3$ (mod $8$), and so we've obtained a contradiction. Hence our assumption was wrong, and $\ell = 0.$ This implies the result. $\square$