3
$\begingroup$

Find all the natural numbers $n$ such that $\sigma(n)=15$

Where $\sigma (n)$ is the sum-of-divisors function

My attempt:

$$n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}$$

$$\sigma(n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdots \frac{p_s^{\alpha_s+1}-1}{p_1-1}=15$$

$1.\quad \text{ for }s=1:$

$$n=p^\alpha,\quad \frac{p^{\alpha+1}-1}{p-1}=15$$

$$p^{\alpha+1}-1=15p-15\\ p^{\alpha+1}=15p-14$$

I don't know what I should do now.

$\endgroup$
  • 9
    $\begingroup$ $15$ is quite small. With $\sigma(n) \geqslant n$, you can brute-force it in no time. It's the quickest way. $\endgroup$ – Daniel Fischer May 30 '16 at 13:54
  • $\begingroup$ Is this always true? $\sigma (n)\geqslant n$? @DanielFischer $\endgroup$ – Error 404 May 30 '16 at 14:11
  • $\begingroup$ Yes, $n$ is a divisor of $n$. And for $n > 1$, we have $\sigma(n) \geqslant n+1$ (with equality if and only if $n$ is prime). $\endgroup$ – Daniel Fischer May 30 '16 at 14:13
3
$\begingroup$

The suggestion in the comments to use brute force is a little unsatisfactory; what if $15$ were $15000$? Here is a general method.

Suppose $$m = \sigma(n) = \prod_{p^k ||\: n} \frac{p^{k+1}-1}{p-1}.\tag{1}$$ Each factor $d$ in the product is an integer (a finite geometric series). The prime factorization of $m$ will severely restrict the possible multiplicands on the r.h.s. of (1), and then their unusual shape (viz. $\frac{p^{k+1}-1}{p-1}$) will reveal much about the prime factorization of $n$.

To wit, if $d$ divides $m$ and $\frac{p^{k+1} - 1}{p-1} = d$ then $p^{k+1} = pd - (d - 1)$ which means $p$ divides $d-1$. This yields one equation to solve per prime $p$ dividing $d-1$, namely the following equation: $$p^k = d - \frac{d-1}{p}.\tag{2}$$

Already we can see that $d = 1$ is forbidden, since it implies $p^k = 1$, which is absurd (contradicts the fundamental theorem of arithmetic). Thus the general procedure is to consider a factor $d \ne 1$ of $m$ and check, for each prime $p$ under $d-1$, whether the r.h.s. of (2) is a power of $p$; if so, repeat the process replacing $m$ by $m/d$ (and excluding the prime $p$ from further consideration). This can get complicated; luckily we are dealing here only with $m = 15 = 3 \cdot 5$, a semiprime.

If $d = 3$ then $p \mid 2$ so $p = 2$ and (2) becomes $2^k = 2$ which means $k = 1$. Thus, possibly, $n$ is singly even. However, moving on to the complementary divisor $15/3 = 5$, if $d = 5$ then $p \mid 4$ so $p = 2$ and this is a problem: the prime $2$ was supposed to contribute only one term in the r.h.s. of (1). [If this is unconvincing, use (2) again: $2^k = 3$ which can't happen ($k \in \mathbf{Z}$).] Thus the appearance of $5$ and $3$ together in the r.h.s. of (1) is inconsistent.

That leaves us with $d = 15$. This implies $p \mid 14$ so $p = 2$ or $7$. But $7^k = 13$ can't happen. On the other hand, $2^k = 8$ has the solution $k = 3$, and this is the only consistent description of $n$ we can glean.

It remains to check that $n = 2^3 = 8$ works: $\sigma(8) = 1 + 2 + 4 + 8 = 15$ ($ = 1111_2$ in binary!) so, yes!

$\endgroup$
1
$\begingroup$

Here is a way to finish the s = 1 case in the way you started it and continuing from your last line:

$(p^\alpha - 15)p = 14$.

Since p is prime and divides 14 we must have either $p = \pm 2$ or $p = \pm 7$. So we are left with four cases: $2^\alpha - 15 = 7$, $2^\alpha - 15 = -7$, $7^\alpha - 15 = -2$ and $7^\alpha - 15 = 2$. It is easy to see that in only one case $\alpha$ is an integer, which means that there is exactly one solution to the $s = 1$ case.

Time to move on to s = 2. Here it useful that there are not that many ways to write 15 as the product of 2 integers. So we can either solve the system of two equations:

$(p^{\alpha + 1} - 1)/(p-1) = 15$ and $(q^{\alpha + 1} - 1)/(q-1) = 1$

or the system of two equations

$(p^{\alpha + 1} - 1)/(p-1) = 3$ and $(q^{\alpha + 1} - 1)/(q-1) = 5$

Of course all of them take some work, and after solving this we have to move on two s = 3, but as Daniel points out above, we won't be busy for ever. You will find that in order to solve the s = 3 case you are looking at equations you already studied in the s = 2 case and so on. (Note for instance that of the four equations needed in the s = 2 case, the first has already been studied when working on s = 1.)

Good luck!

(With many thanks to Daniel for below comment!)

$\endgroup$
  • $\begingroup$ $2^{\alpha} - 15 = -7$, and $\alpha = 3$ gives you $\sigma(8) = 15$. $\endgroup$ – Daniel Fischer May 30 '16 at 14:50
  • $\begingroup$ aargh of course! Thank you! I will edit my answer $\endgroup$ – Vincent May 30 '16 at 14:51

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.