Find all integers $n$ satisfying $n \geq 2$ and $\dfrac{\sigma(n)}{p(n)-1} = n$, in which $\sigma(n)$ denotes the sum of all positive divisors of $n$, and $p(n)$ denotes the largest prime divisor of $n$.
Problem
Source: APMO 2023 Problem 2
Tags: number theory, APMO, APMO 2023
05.07.2023 22:26
Disappointing problem. Just use the bound $\frac{\sigma(n)} {n} \leq \omega(n)$ from Baltic Way 2022 P17 and realize that you are done.
05.07.2023 22:48
Sketch : The obvious way to deal with this type of problem is to take the generalized case of $n$ as the prime factorization of it. Like suppose $n=\prod_{i=1}^{m} p_{i}^{\beta_i}$ where $p_i$ are primes such that $p_m > p_{m-1} > .....>p_1$. Now to get a bound on $m$. Now see what we know $p(n)=p_m, \sigma(n)=\prod_{i=1}^{m}(1+\sum_{j=1}^{\beta_{i}} p_i ^{{j}})$. Now get that $p_{m}-1 =\frac{\sigma(n)}{n} < \prod_{i=1}^{m}(1+\sum_{j=1}^{\beta_{i}} \frac{1}{p_{i}^j}) < m+1$ which is only possible when $m \leq 2$. Now case checking gives $n=6$ as the only answer. (will attach the full solution later )
05.07.2023 22:56
If $n=p_1^{e_1}\cdots p_k^{e_k}$ where $p_1<\cdots<p_k$ then $$\frac{\sigma(n)}{n}=\prod_{i=1}^k \frac{p_i^{e_i+1}-1}{p_i^{e_i+1}-p_i^{e_i}} \leq \prod_{i=1}^k \frac{p_i}{p_i-1}.$$I claim that if $p_k\geq 5$ then this quantity is less than $p(n)-1$. This is by induction with base cases trivial, since if we add some prime factor $p_{k+1}$ then the product increases by a factor of $\tfrac{p_{k+1}}{p_{k+1}-1}$ but the value of $p(n)-1$ increases by a factor of $\tfrac{p_{k+1}-1}{p_k-1}$, which is greater than the first fraction. Therefore we reduce the problem to $n=2^a3^b$. We want to solve $(2^{a+1}-1)(3^{b+1}-1)=2^{a+2}3^b$. For $a \geq 1$ the first LHS product is at least $3\cdot 2^{a-1}$ and for $b \geq 1$ the second LHS product is at least $8\cdot 3^{b-1}$, we get that the LHS is always at least $2^{a+2}3^b$. These equalities are only sharp when $a=1$ and $b=1$, so $n=6$ is the only answer. $\blacksquare$
06.07.2023 00:12
06.07.2023 00:15
It's obvious that $$p(n)-1=\frac{\sigma(n)}{n}=\prod_{p^k||n}\frac{\sigma(p^k)}{p^k}<\prod_{p^k||n}\left(1+\frac{1}{p}+\frac{1}{p^2}+\cdots\right) \le \prod_{p\le n}\left(1+\frac{1}{p-1}\right)$$Which implies that $$p(n)\le \prod_{p\le p(n)}\left(1+\frac{1}{p-1}\right)$$Notice that for $p(n)=5$ this inequality does not hold true and it's easy to see that the LHS increases faster than the RHS, implying that $p(n)<5$ is required. Thus $n=2^x\cdot 3^y$ and we hence want $2^{x+2}3^y=(2^{x+1}-1)(3^{y+1}-1)$. Since $3\nmid 3^{y+1}-1$ we have $3^{y+1}-1=2^{x+2}$ and hence by Catalan's conjecture we need $x=y=1$. Thus $n=6$ is the only answer (which works).
06.07.2023 03:50
If $n$ had only one prime divisor $p$, then $n=p^k$ and $\sigma(n)=p^k+\ldots+1$ which is not a multiple of $p^k$. Now, assume that $n={p_1}^{k_1} \cdots {p_\ell}^{k_\ell}$ with $\ell \geq 2$ and $p_i$ being prime with $p_1<\ldots<p_\ell$. Note that $p_\ell-1=\dfrac{\sigma(n)}{n}=\prod_{i=1}^{\ell-1} \dfrac{{p_i}^{k_i+1}-1}{(p_i-1){p_i}^{k_i}} \cdot \dfrac{{p_\ell}^{k_\ell+1}-1}{(p_\ell-1){p_\ell}^{k_\ell}}<\prod_{i=1}^{\ell-1} \dfrac{p_i}{p_i-1} \cdot \dfrac{{p_\ell}^{k_\ell+1}-1}{(p_\ell-1){p_\ell}^{k_\ell}}<\prod_{i=1}^{\ell-1} \dfrac{2}{2-1} \cdot \dfrac{p_\ell}{p_\ell-1}=\dfrac{\ell p_\ell}{p_\ell-1},$ and so $(p_\ell-1)^2<\ell p_ \ell$. However, $p_\ell \geq \ell+1$, and so if we let $p_\ell=\ell+1+m$ with $m \geq 0$, we obtain that $(\ell+m)^2 <\ell(\ell+m+1),$ or equivalently that $\ell>\ell m +m^2,$ which is a contradiction if $m \geq 1$. Therefore, $p_\ell=\ell+1$, and so the $p_i$ must be consecutive, which is possible only when $\ell=2$ and $p_1=2,p_2=3$. Therefore, $n=2^{k_1}3^{k_2}$ for some $k_1,k_2$. The given relation rewrites as $(2^{k_1+1}-1)(3^{k_2+1}-1)=4 \cdot 2^{k_1} \cdot 3^{k_2}.$ This readily implies that $2^{k_1+1}-1=m3^{k_2}$ and $3^{k_2+1}-1=n2^{k_1}$ for some $m,n$ such that $mn=4$, and since $m$ must be odd for $\pmod 2$ reasons, $m=1$ and $n=4$ which easily gives (e.g. using the Catalan conjecture) that $k_1=k_2=1$. Thus, the only solution is $n=6$.
13.07.2023 07:36
$\sigma(n)$ is very strong compared to $p(n)$ and $n$ so it sets up an incredibly rigid constraint on $n$. Let $n = \Pi_{i=1}^k p_i^{a_i}$, such that $p_1 > p_2 > \ldots > p_k$. Then, the question is $\Pi_i({\Sigma_{j=0}^{a_i}{\frac{1}{p_j}}}) = p_1 -1$. Sending all $a_i$ to infinity gives $RHS < k+1$, which means that $p_1 \leq k+1$. This is only possible if $(p_1,k) = (2,1), (3,2)$. The question is complete through simple computation on $n = 2^a3^b$
15.07.2023 02:20
We claim that the answer is 6 only. Rearrange the equation to $$\frac{\sigma(n)}{n}=p(n)-1$$since $\sigma{n}/n$ is a much nicer function to deal with (it is multiplicative). Claim: $n$ cannot have a prime factor $p\geq 5$. Suppose otherwise. Then, let $p$ be the largest prime factor. The contribution of a prime factor $q$ to $\frac{\sigma(n)}{n}$ is at most a multiplier of $\frac{q}{q-1}$ by geometric sequence, and clearly $p-1$ is not prime, so $$\frac{\sigma(n)}{n}<\frac{2}{1}\frac{3}{2}\cdots \frac{p-2}{p-3}\frac{p}{p-1}\leq \frac{p(p-2)}{p-1}.$$Clearly, we have $$\frac{p(p-2)}{p-1}<p-1,$$which is a contradiction. Hence, $n$ cannot have a prime factor that is at least 5. Thus, it remains to show the case for when $p(n)=2$ and $p(n)=3$. $p(n)=2$ clearly does not work, as $\sigma(2^k)=2^{k+1}-1$. If $p(n)=3$, then $$n=2^a3^b.$$Furthermore, $$\sigma(n)=(2^{a+1}-1)(\frac{3^{b+1}-1}{2}),$$so we wish to have $$(2^{a+1}-1)(3^{b+1}-1)=4\cdot 2^a\cdot 3^b.$$For any $a\geq 2$, $2^{a+1}-1$ has some prime factor at least 5 (e.g. by Zsigmondy) so it cannot match the RHS, and similar for $3^{b+1}-1$, so it suffices to check $a,b\leq 1$, which gives $a=b=1$ for an answer of 6 only.
25.10.2023 19:54
The only answer is $n=6$ which works. Claim: $p(n)$ must be $2$ or $3$. Proof. Let $n=p_1^{q_1}\cdot p_2^{q_2}\cdot \dots\cdot p_k^{q_k}$. Then, we need \[\frac{\prod_{i=1}^{k} \left(p_i^{q_1}+p_i^{q_i-1}+\dots + 1\right)}{p(n)-1}=\prod_{i=1}^k p_i^{q_i}\]Now, rewrite this as \[p(n)-1=\prod_{i=1}^j\left(1+\frac{1}{p_i}+\dots +\frac{1}{p_i^{q_i}}\right) <\prod_{i=1}^k\sum_{j=0}^{\infty}p_i^{-j}=\prod_{i=1}^{k} \frac{p_i}{p_i-1} \leq \prod_{p\leq p(n)}\frac{p}{p-1}\]Now, for $p=5$ the left hand side is $4$ while the right hand side is $\frac{15}{4}$ which doesnt work. Inductivly, we can show that for $p_i\geq 5$ that $p_i-1>\prod_{p\leq p_i}\frac{p}{p-1}$ as multiplying each side by $\frac{p_{i+1}}{p_{i+1}-1}$ gives \[\prod_{p\leq p_{i+1}}\frac{p}{p-1}<p_i\cdot \frac{p_{i+1}}{p_{i+1}-1} \leq \frac{(p_{i+1}-2)p_{i+1}}{p_{i+1}-1}<p_{i+1}-1\]as desired. $\blacksquare$ Now, if $p(n)=2$ there are no solutions. Thus let $n=2^a 3^b$ with $b>0$. Then, \[2^a \cdot 3^b=\frac{(1+2+\dots + 2^a)(1+3+\dots + 3^b)}{2} \iff 1-\frac{1}{2^{a+1}}=\frac{2\cdot 3^b}{3^{b+1}-1}\]If $b\geq 2$ then the right handside is between $\frac 12$ and $\frac 34$ so there are no solutions. Thus $b=1$ giving $a=1$ as claimed.
18.01.2024 06:48
Who knows which country will be coordinating at the APMO 2024?
26.03.2024 08:12
@nagibator I think SL, not sure