$165=(3) (5) (11)$

$\sigma (p^a)$=$p^{a+1}-1 \over {p-1}$=$3$



Got stuck here. How do I proceed?


There is a product-of-prime-series formula for $\sigma(n)$. If the prime factorisation of $n$ is $\prod_{i=1}^rp_i^{a_i}$: $$\sigma(n)=\prod_{i=1}^r\sum_{j=0}^{a_i}p_i^j$$ We make a table of $\sum_{k=0}^ap^k$ for small primes $p$ and exponents $a$. For each prime, we stop listing sums of exponents if they would surpass 165:

  p | 0   1   2   3   4   5   6
  2 | 1  (3)  7 (15) 31  63 127
  3 | 1   4  13  40 121
  5 | 1   6  31 156
  7 | 1   8  57
 11 | 1  12 133
 13 | 1  14
... | ...
163 | 1 164

We seek the numbers 3, 5, 11, 15, 33, 55 and 165 – the divisors of 165 except 1 – in the table. If we can find any subset of those numbers that lies in distinct rows and whose product is 165, we can use the multiplicative property of the divisor function to construct a $k$ with $\sigma(k)=165$.

Except that we can't find any such subset: only 3 and 15 appear in the table (they are marked with brackets). Hence we conclude that there is no $k$ with $\sigma(k)=165$. Indeed, A007369, the numbers $n$ such that $\sigma(x)=n$ has no solution, contains 165.

  • $\begingroup$ in the reverse way it is easier. For any $d | 165$, find if $d = \sum_{m=0}^k p^m$ for some prime $p$. We get $3 = 1+2$, and that's all $\endgroup$ – reuns Oct 30 '16 at 3:56
  • $\begingroup$ @LEMONS4Head $165 = 3.5.13$ so we need to find if $\sigma(p^k) = 3$ or $5$ or $13 $ or $165$ (for small $p$). And it happens that there is only $\sigma(2) = 3$ , the other divisors of $165$ don't correspond to $\sigma(p^k)$ $\endgroup$ – reuns Oct 30 '16 at 4:37
  • $\begingroup$ @user1952009 $3.5.13=195$. $3.5.11=165$. Which is what confuses me. Parcly continued the list to p=13 instead of stopping at 11. I guess it didn't make a difference in the long run, but still. $\endgroup$ – LEMONS4Head Oct 30 '16 at 4:46
  • $\begingroup$ @LEMONS4Head Yes right, 11 not 13 :) so who cares of Parcly's answer ? Compute $\sigma(p^k)$ for small $p$ and check yourself $\endgroup$ – reuns Oct 30 '16 at 4:47
  • $\begingroup$ @LEMONS4Head I continued it to $p=13$ because I think it looks better that way (you could intuitively guess that all the intervening rows to $p=163$ only contain 1, $p$ and then $p^2>165$). For actually finding the numbers multiplying to 165, only the numbers to the right of the 1's matter. $\endgroup$ – Parcly Taxel Oct 30 '16 at 4:51

The easy way: look at a table of $\sigma(k)$ for $k \le 164$, e.g. the one at OEIS sequence A000203 and pick out the value $165$.

  • $\begingroup$ Yes but...is there another way $\endgroup$ – LEMONS4Head Oct 30 '16 at 2:46

Proceeding step-by-step to look for possible $n$ such that $\sigma(n) = 165$:

For prime $p$, $\sigma(p)=p+1$. Since $164$ is not prime, this is not a possibility for $\sigma(n) = 165$.

Next for prime power $p^k$, $\sigma(p^k)=p^k + p^{k-1} + \cdots + p+1$. For $p=2$ we also know that $\sigma(2^k)=2^{k+1}-1$ . Since $166$ is not a power of $2$, $n=2^k$ is not feasible. For other primes, we can also observe that for odd $p$, this sum is odd iff $k$ is even. So we can quickly evaluate $\sigma(p^k)$ for the small even powers of primes $3,5,7,11$ and we will know that higher primes are not feasible (since $13^2>165$):

\begin{array}{c|c} p & k & \sigma(p^k)\\\hline 3 & 2 & 13\\ 3 & 4 & 121\\ 5 & 2 & 31\\ 7 & 2 & 57\\ 11 & 2 & 133\\ \end{array}

None of these numbers are $165$, showing that $n = p^k$ is not a feasible solution.

Also, none of them divide $165$ (even though $\sigma(2)$ and $\sigma(8)$ do). Since $\sigma$ is multiplicative between prime powers (that is, $\sigma(p^kq^m) = \sigma(p^k)\sigma(q^m)$), this means that there are no solutions to $\sigma(n) = 165$, since we require more than one prime divisor.

  • $\begingroup$ How do you know that $\sigma(p^k)$ is odd iff $k$ is even? $\endgroup$ – LEMONS4Head Oct 30 '16 at 4:10
  • $\begingroup$ @LEMONS4Head for odd $p$, the running sum of powers (including $p^0=1$) is only odd when there are an odd number of terms, which makes the largest power even. $\endgroup$ – Joffan Oct 30 '16 at 4:49
  • $\begingroup$ how can you disregard the fact that $\sigma(2)$ and $\sigma(8)$ divide 165? $\endgroup$ – LEMONS4Head Oct 30 '16 at 5:24
  • $\begingroup$ Is it because 2 and 8 are not relatively prime? So the multiplicative property of $\sigma$ doesn't apply? $\endgroup$ – LEMONS4Head Oct 30 '16 at 6:13
  • $\begingroup$ We already know $n$ can't just be a power of $2$, so we need another prime involved - but none of the possible candidates produce a suitable divisor of $165$. $\endgroup$ – Joffan Oct 30 '16 at 6:54

Since it seems that you are looking for the "hard" way:

Let $n$ be a positive integer such that $\sigma(n)=165.$ Then $\prod_{p\mid n}(p^{\alpha_p+1}-1)/(p-1)=3\cdot5\cdot11,$ where the product is taken over all primes dividing $n$ and where $\alpha_p$ is the exponent of $p$ in the prime decomposition of $n.$ Now note that if $p\mid n$ then $\alpha_p+1\geqslant2$ so $(p^{\alpha_p+1}-1)/(p-1)>1.$ Hence, since the RHS of the equality above has exactly three prime factors, $n$ has at most three prime factors. If $n=p^a$ for some prime $p$ and some integer $a>0$ then $\sigma(n)=(p^{a+1}-1)/(p-1)$ so $164=2^2\cdot41=p(165-p^a)$ so $p\in\{2,41\}.$ It is easy to check that none of these works. Thus $n$ has either two or three prime factors. If $n=p^aq^b,$ with $p$ and $q$ primes, $p\neq q$ and $a,b>0$ then we have three possibilities. If we set $\alpha:=(p^{a+1}-1)/(p-1)$ and $\beta:=(q^{b+1}-1)/(q-1),$ the three possibilities are:

$(i)$ $\alpha=15$ and $\beta=11.$ Then $14=2\cdot7=p(15-p^a)$ so $p\in\{2,7\}.$ In the same way we find that $q\in\{2,5\}.$ If $p=2$ then $a=3$ and also since $p\neq q$ and $10=2\cdot5=q(11-q^b)$ then $q=5$ so $5^b=9,$ which is impossible. If $p=7$ then $7^a=13,$ which is impossible.

$(ii)$ $\alpha=33$ and $\beta=5.$ Then $32=2^5=p(33-p^a)$ so $p=2.$ Also $4=2^2=q(5-q^b)$ so $q=2,$ which contradicts the fact that $p\neq q.$

$(iii)$ $\alpha=3$ and $\beta=55.$ Then $2=p(3-p^a)$ so $p=2$ and $a=1.$ Also $54=2\cdot3^3=q(55-q^b)$ and since $q\neq p$ then $q=3$ and thus $3^b=37,$ which is impossible.

It remains to see what happens when $n=p^aq^br^c,$ where $p,q,r$ are pairwise distinct primes and $a,b,c$ are positive integers. Now note that there is only one possibility, which is $(p^{a+1}-1)/(p-1)=3,$ $(q^{b+1}-1)/(q-1)=5$ and $(r^{c+1}-1)/(r-1)=11.$ Then $p=q=2,$ which contradicts the fact that $p\neq q. $ Thus there is no $n$ with $\sigma(n)=165.$


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.