For every positive integer $N$, let $\sigma(N)$ denote the sum of the positive integer divisors of $N$. Find all integers $m\geq n\geq 2$ satisfying \[\frac{\sigma(m)-1}{m-1}=\frac{\sigma(n)-1}{n-1}=\frac{\sigma(mn)-1}{mn-1}.\] Ankan Bhattacharya
Problem
Source: USA TSTST 2020 Problem 8, by Ankan Bhattacharya
Tags: USA, TST, number theory, Tstst
25.01.2021 20:00
25.01.2021 20:02
We claim that the only solutions occur when $m$ and $n$ are both powers of the same prime $p$. This works as we always have $$\frac{\sigma(p^k) - 1}{p^k - 1} = \frac{\frac{p^{k+1} - 1}{p - 1} - 1}{p^k - 1} = \frac{p^{k+1} - p}{(p^k - 1)(p - 1)} = \frac{p}{p-1}$$irrespective of $k > 0$ and $m$, $n$, $mn$ would all be some power of $p$. Now we eliminate all other possibilities. Observe that if $\tfrac{a}{b} = \tfrac{c}{d}$, then $\tfrac{a}{b} = \tfrac{a+c}{b+d} = \tfrac{c}{d}$. Hence \begin{align*} \frac{\sigma(m) - 1}{m - 1} &= \frac{[\sigma(mn)-1] - [\sigma(m)-1] - [\sigma(n)-1]}{[mn-1] - [m-1] - [n-1]} \\ &= \frac{\sigma(mn) - \sigma(m) - \sigma(n) + 1}{(m - 1)(n - 1)} \\ \implies (n - 1)(\sigma(m) - 1) &= \sigma(mn) - \sigma(m) - \sigma(n) + 1 \\ \implies 0 &= \sigma(mn) - n\sigma(m) - (\sigma(n) - n) \end{align*} Now switch to the definition of $\sigma$ as a summation. We interpret \begin{align*} \sigma(mn) - n\sigma(m) - (\sigma(n) - n) &= \sum_{d|mn} d - \sum_{d|m} nd - \left(\sum_{d|n} d - n\right) \\ &= \sum_{d|mn} d - \sum_{\substack{d|mn \\ n|d}} d - \sum_{\substack{d|n \\ n \nmid d}} d \\ &= \sum_{\substack{d|mn \\ n \nmid d}} d - \sum_{\substack{d|n \\ n \nmid d}} d \\ &= \sum_{\substack{d|mn \\ d \nmid n \\ n \nmid d}} d \end{align*}Of note is that this expression is always nonnegative and we require the case where the set $S_{n} = \{d \mid d|mn, d \nmid n, n \nmid d \}$ is empty. Clearly we may also switch the roles of $m$ and $n$. Now suppose for the sake of contradiction that there exist two distinct primes $p, q | mn$. If $p|m$ and $q|n$ then $n \cdot \tfrac{p}{q} \in S_{n}$ and vice versa, impossible. Therefore, $p$ and $q$ both cannot divide at least one of $m$ and $n$. Repeating this argument over all primes that may divide $mn$ we find that all such primes cannot divide one of $m$ or $n$, proving that at least one is $1$. But we were given $m, n \geq 2$, contradiction. Hence $mn$ is a prime power which proves $m$ and $n$ both are as well. This completes the proof. $\blacksquare$
26.01.2021 06:48
Haven't seen any size bashes yet, so... here's this. Let $p$ be a prime dividing $n$. Let $e = \nu_p(m), f = \nu_p(n)$. Then $$\frac{\sigma(mn)}{n\sigma(m)} \ge \frac{1 + \frac{1}{p} + \ldots + \frac{1}{p^{e+f}}}{1 + \frac{1}{p} + \ldots + \frac{1}{p^e}}$$ For convenience, let $X$ and $Y$ be the numerator and denominator of this fraction. Note clearly $\frac{\sigma(mn) - 1}{mn-1} > \frac{\sigma(mn)}{mn} \ge \frac{X}{Y}\frac{\sigma(m)}{m}$. Then we cannot have $$\frac{X}{Y}\frac{\sigma(m)}{m} \ge \frac{\sigma(m)-1}{m-1}$$$$\iff (m-1)X\sigma(m) \ge mY(\sigma(m) - 1)$$$$\iff mY \ge \sigma(m)(mY-(m-1)X)$$ This is clearly satisfied if $(m-1)X \ge mY$ $$\iff m(X-Y) \ge X$$$$\iff m\left(\frac{1}{p^{e+1}} + \ldots + \frac{1}{p^{e+f}}\right) \ge 1 + \frac{1}{p} + \ldots + \frac{1}{p^{e+f}}$$ Now if $m \ge p^e(p+2)$, the LHS is at least $\frac{m}{p^{e+1}} = 1 + \frac{2}{p} > RHS$, so we get no solutions. Thus for any prime $p \mid n$, we have $\frac{m}{p^e} \le p+1$. Forget $m \ge n$ and let $p$ be the smallest prime dividing one of $m, n$, say $p \mid n$. Then any prime factor of $\frac{m}{p^e}$ is greater than $p$. If $p$ is odd, $p+1$ is even and nonprime, so this implies $m = p^e$. Then applying the same argument gives that $n$ is power of $p$ and we are done. Now suppose $p = 2$. Case 1: $m = 2^e$ We claim $n = 2^f$. If not, $n = 3 \times 2^f$. But then $\frac{\sigma(n) - 1}{n-1}$ is the ratio of two odd integers while $\frac{\sigma(m) - 1}{m-1}$ is the ratio of an even integer to an odd integer. Case 2: $m = 3 \times 2^e$, $e \ge 1$. $n = 2^f$ is ruled out identically to case 1, so say $ n = 3\times 2^f$. Then $\frac{\sigma(mn)-1}{mn-1}$ is the ratio of two odd integers while $\frac{\sigma(m) - 1}{m-1}$ is even over odd. Case 3: $m = 3$ Then $\frac{\sigma(3) - 1}{3-1}$ is an odd over an even, while $\frac{\sigma(n)-1}{n-1}$ is an integer over an odd. Thus the only solutions are when $m$ and $n$ are powers of the same prime, which are easily verified to work.
07.02.2021 16:25
$\boxed{\text{Answer:} \ (m,n) = (p^e,p^f)}$ for $p$ prime, $e \geq f \in \mathbb{N}$. It is easy to verify by direct expansion that they work. Again, TST $\#8$ is probably the hardest problem from all 8 problems $\textit{which aren't Beluhov's}$ --- and that's saying something about the difficulty of the third test, considering the finale is Beluhov's. A half-rigorous-bash and a half-organically done Solution. Heavy on $``\text{additive}"$ combinatorics and set bijections. $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Dimensional Transfer.}$ First we dirty our hands by expanding it without loosening the equality's strength. \[\frac{\sigma(m)-1}{m-1}=\frac{\sigma(mn)-1}{mn-1}\]first implies \[ mn \cdot \sigma(m)-mn+\sigma(mn) = m \cdot \sigma(mn)- m+\sigma(m)\]Looking these as operations in sets (of numbers which divides $m^2n$): $mn \cdot \sigma(m)$ is the (sum of the elements) of the set $M_1 = \{d; mn \ \text{divides} \ d\}$, $mn$ is the element $mn$, $\sigma(mn)$ is represented by the set $M_2 = \{d; d \ \text{divides} \ mn \}$. adding all of these up, the LHS creates an interesting duality: for the LHS is the sum of numbers which divides $mn$ or are a multiple of $mn$. Here, the solely double-counted term $mn$ is removed, making the set $M_{\cup}(L) = M_1-\{mn\}+M_2$ equal to the simple definition of $M_1 \cup M_2$. Here I unambigously add $\textbf{with considering}$ the multiplicity of their elements, in support of the original additive statement. The RHS further corroborates the LHS's duality by a similar definition --- $mn$ just needs to be replaced with $\dfrac{m^2n}{mn} = m$. Define $M_{\cup}(R)$ to replace the union of the RHS's sets. Further so, the expression \[\frac{\sigma(n)-1}{n-1}=\frac{\sigma(mn)-1}{mn-1}\]also can be expanded and given a similar notation: $N_{\cup}(L)$ and $N_{\cup}(R)$ . Here, the problem statement is equivalent to saying that $\sum_{m \in M_{\cup}(L)} m - \sum_{m \in M_{\cup}(R)} m = 0$, or $\sum_{m \in M_{\cup}(L)-M_{\cup}(R)} m = \sum_{m \in M_{\cup}(R)-M_{\cup}(L)} m$. and saying the same for $n$, too. $\color{green} \rule{25cm}{2pt}$ Now to finish this preliminary exposition, I will say (for ease of interpretation) to see this as an $d$-dimensional block; where $d$ is the number of unique prime divisors of $mn$. In regards to basic definitions: each dimension corresponds to prime divisors of $mn$ --- and each node in that $``\text{rectangular}"$ block corresponds to a divisor of $m^2n$ in the first expression or $mn^2$ in the second expression. Then, the union set $M_{\cup}(L)$ can be obtained by fixing the node $mn$ and selecting all nodes which have either (all measures at most of $mn$'s) or (all measures at least of $mn$'s). The statement in the list nicely corresponds to saying that the sum of numbers that is $\textbf{in one union but not the other}$ is equal to the sum of numbers that is $\textbf{in the other union but not in the first union}$. $\color{magenta} \rule{25cm}{2pt}$ Next, we decimate the suspiciously looking equality between the sets $M_{\cup}(L)-M_{\cup}(R)$ and $M_{\cup}(R)-M_{\cup}(L)$ --- to be more exact, we will derive a contradiction using $\textbf{both absurd equalities}$ between the $M$s and $N$s. $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{Double Dilation (Combinatorics Alert).}$ We claim that \[ \{N_{\cup}(R)-N_{\cup}(L)\} = \{M_{\cup}(L)-M_{\cup}(R)\} \times n \]where $A \times c = \{ b \mid b = a \cdot c \ \text{for} \ a \in A, c \in \mathbb{R}\}$. Furthermore, in a similar manner, \[ \{N_{\cup}(L)-N_{\cup}(R)\} = \{M_{\cup}(R)-M_{\cup}(L)\} \times \dfrac{1}{m} \]$\color{red} \textbf{Proof.}$ This is easy bijection (though not easy to conjure, of course ...) We will prove the first statement only, since the second can be attained by switching the roles of $M$ and $N$. First, note that the elements of $M_{\cup}(L)-M_{\cup}(R)$ can only originate from the bottom-left (or the low-measure) part of $M_{\cup}(L)$ --- it's easy to prove that all high-measured parts (i.e. those divisible by $mn$) are also covered by the high-measured set of $M_{\cup}(R)$ (i.e. those divisible by $m$ will also consist of those divisible by $mn$.) So, the elements of (that set) will consist of those which divides $mn$, is divisible by $1$ (duh!), but not divisible by $m$ or a factor of $m$. Moving our attention towards the set $N_{\cup}(R)-N_{\cup}(L)$; their members can only originate from the top-right (high-measured) part of $N_{\cup}(R)$ --- those divisible by $n$. Note that all nodes which are factors of $mn$ or are divisible by $mn$ are automatically out, so the remaining members are those which divides $mn^2$, is divisible by $n$ (see the pattern?), but not divisible by $mn$ or a factor of $mn$.
These two sets are equal to a factor of $n$. Magic casted. $\blacksquare$ $\blacksquare$ $\color{blue} \rule{25cm}{1pt}$ $\color{blue} \textbf{Finishing.}$ Assume the dimension is greater than 1 ($d \ne 1$ happens iff $mn \ne p^{e+f}$ happens) --- so the sets described in $\color{red} \textbf{Double Dilation (Combinatorics Alert)}$ are nonempty (and positive). So, assuming from $\color{green} \textbf{Dimensional Transfer}$'s first conclusion that the $\textbf{element-sums}$ of $\{N_{\cup}(R)-N_{\cup}(L)\}$ and $\{N_{\cup}(L)-N_{\cup}(R)\}$ are equal (let's say both of them are $S$): there is no way for the element sums of $\{M_{\cup}(L)-M_{\cup}(R)\} = \dfrac{S}{n}$ and $\{M_{\cup}(R)-M_{\cup}(L)\} = S \cdot m$ are equal. Q.E.D. $\blacksquare$ $\blacksquare$ $\blacksquare$
30.04.2021 19:17
Write, $m = p_1^{\alpha_1} \cdots p_k^{\alpha_k} ~,~ n = p_1^{\beta_1} \cdots p_k^{\beta_k}$ , for distinct primes $p_1 < p_2 < \cdots < p_k$ and non-negative integers $\alpha_1,\cdots,\alpha_k,\beta_1,\cdots,\beta_k$. Then, \begin{align*} \frac{\sigma(mn)}{\sigma(m)} < \frac{\sigma(mn)-1}{\sigma(n)-1} = \frac{mn-1}{n-1} = n + \frac{n-1}{m-1} \le n + \frac{n}{m} ~~\implies ~~ \boxed{\frac{\sigma(mn)}{\sigma(n)} < n + \frac{n}{m}} ~~ ; \\ \sigma(mn) = \prod_{i=1}^k \frac{p_i^{\alpha_i + \beta_i + 1} - 1}{p_i - 1} ~~~,~~~ \sigma(m) = \prod_{i=1}^k \frac{p_i^{\alpha_i +1} - 1}{p_i-1} ~~ \implies T = \frac{\sigma(mn)}{\sigma(n)} = \prod_{i=1}^k \frac{p_i^{\alpha_i + \beta_i + 1}-1}{p_i^{\alpha_i + 1} - 1} = \prod_{i=1}^k p_i^{\beta_i} + \frac{p_i^{\beta_i} - 1}{p_i^{\alpha_i + 1} - 1} \end{align*}Note that $n$ must divide $m$: Otherwise, if for some $1 \le i \le k$, $\beta_i \ge \alpha_i + 1$, then we easily get $T \ge n+1$, which contradicts $(1)$. So we can now even assume that all the $\alpha_i \text{'s}$ are positive integers. Next we claim that $k =1$: Otherwise, if $k \ge 2$, then, $$n + \frac{n}{m} > \frac{\sigma(mn)}{\sigma(n)} \ge \left( p_1^{\beta_1} + \frac{p_1^{\beta_1} - 1}{p_1^{\alpha_1 + 1} - 1} \right) \left(\frac{n}{p_1^{\beta_1}} \right) ~~ \stackrel{\text{simplification}}{\implies} ~ \frac{1}{m} > \frac{p_1^{\beta_1} - 1}{p_1^{\beta_1}(p_1^{\alpha_1+1}-1}$$But $m \ge p_1^{\alpha_1 + 1}$, and so we obtain $ \frac{p_1^{\alpha_1 + 1} - 1}{p_1^{\alpha_1+1}} < \frac{p_1^{\beta_1 - 1}}{p_1^{\beta_1}} ~~ \implies ~ p_1^{\alpha_1 + 1} < p_1^{\beta_1} ~~ \implies ~ \alpha_1 < \beta_1$ Which contradicts the fact that $m$ is a multiple of $n$. Thus $k=1$. So now, $m = p^a ~,~n=p^b ~, ~ mn = p^{a+b}$ for some prime $p$ and positive integers $a,b$ with $a \ge b$. Then, $\frac{\sigma(m)}{m-1} = \frac{p+\cdots+p^a}{p^a-1} = \frac{p(p^a-1)}{(p-1)(p^a-1)} = \frac{p}{p-1}$. Similarly, both of $\frac{\sigma(n) - 1}{n-1} ~,~ \frac{\sigma(mn)-1}{mn-1}$ also equal $\frac{p}{p-1}$. So the required conditions are also satisfied. Hence, the solution set $S$ for $(m,n)$ is $\boxed{S = \{(p^a,p^b): a,b \text{ are positive integers}, ~ a \ge b, ~ p \text{ is a prime} \}}$. $\blacksquare$ Can someone please check my solution and tell whether it is correct or not ?
30.06.2021 06:48
The answer is $m,n$ are both equal to a certain power of a prime $p$, which obviously works. Now observe that $$\frac{\sigma(mn)-1}{mn-1}=\frac{\sigma(m)-1}{m-1}=\frac{\sigma(n)-1}{n-1}=\frac{n(\sigma(m)-1)+\sigma(n)-1}{n(m-1)+n-1}=\frac{n\sigma(m)-n+\sigma(n)-1}{mn-1}$$Hence $$\sigma(mn)=n\sigma(m)-n+\sigma(n)$$Which implies $$\sigma(mn)-n\sigma(m)=\sigma(n)-n$$Notice that the right hand side is the sum of divisors of $n$ except $n$ it self, which all appears in the left hand side, since they are divisors of $mn$, but not divisble by $n$. Therefore, all divisors of $mn$ which are not divisble by $n$ must also be divisors of $n$, in particular we have $n|m$, and that $m$ has no prime divisors other than those of $n$. Moreover, if $n$ has two distinct prime divisors $p,q$, then $p^{2v_p(n)}|mn$, but it is neither divible by $n$ nor a divisor of $n$, contradiction. Hence $m,n$ must be prime powers as desired.
30.06.2021 08:10
The answer is that $m$ and $n$ should be powers of the same prime number. This is true because because for a prime power we have \begin{align*} \frac{\sigma(p^e) - 1}{p^e - 1} = \frac{(1 + p + \dots + p^e) - 1}{p^e - 1} = \frac{p(1 + \dots + p^{e-1})}{p^e - 1} = \frac{p}{p-1} \end{align*}We will now prove that these are the only ones. Let $\alpha$ be the common value of three fractions. Claim: Any solution $(m,n)$ should satisfy $d(mn) = d(m) + d(n) - 1$ Proof : The divisors of $mn$ include the divisors of $m$ plus $m$ times the divisor of $n$. Let $\alpha$ be the common value ; then this gives : \begin{align*} \sigma(mn) \geq \sigma(m) + m\sigma(n) - m\\ = (\alpha m - \alpha + 1) + m(\alpha n - \alpha + 1) - m\\ = \alpha mn - \alpha + 1 \end{align*}So the equality holds. Thus these are all the divisors of $mn$ , for a count of $d(m) + d(n) - 1$ Claim: If $d(mn) = d(m) + d(n) - 1$ and $\min(m,n) \geq 2$ , then $m$ and $n$ are powers of the same prime. Proof: Let $X$ denote the set of divisors of $m$ and $Y$ denote the set of divisors of $n$. Then $|X \cdot Y| = |X| + |Y| - 1$ and $\min (|X| , |Y|) > 1$. So $|X|$ and $|Y|$ are in geometric progression with the same ratio. It follows that $m$ and $n$ are powers of the same prime. $\blacksquare$
30.06.2021 13:13
Bratin_Dasgupta wrote: The answer is that $m$ and $n$ should be powers of the same prime number. This is true because because for a prime power we have \begin{align*} \frac{\sigma(p^e) - 1}{p^e - 1} = \frac{(1 + p + \dots + p^e) - 1}{p^e - 1} = \frac{p(1 + \dots + p^{e-1})}{p^e - 1} = \frac{p}{p-1} \end{align*}We will now prove that these are the only ones. Let $\alpha$ be the common value of three fractions. Claim: Any solution $(m,n)$ should satisfy $d(mn) = d(m) + d(n) - 1$ Proof : The divisors of $mn$ include the divisors of $m$ plus $m$ times the divisor of $n$. Let $\alpha$ be the common value ; then this gives : \begin{align*} \sigma(mn) \geq \sigma(m) + m\sigma(n) - m\\ = (\alpha m - \alpha + 1) + m(\alpha n - \alpha + 1) - m\\ = \alpha mn - \alpha + 1 \end{align*}So the equality holds. Thus these are all the divisors of $mn$ , for a count of $d(m) + d(n) - 1$ Claim: If $d(mn) = d(m) + d(n) - 1$ and $\min(m,n) \geq 2$ , then $m$ and $n$ are powers of the same prime. Proof: Let $X$ denote the set of divisors of $m$ and $Y$ denote the set of divisors of $n$. Then $|X \cdot Y| = |X| + |Y| - 1$ and $\min (|X| , |Y|) > 1$. So $|X|$ and $|Y|$ are in geometric progression with the same ratio. It follows that $m$ and $n$ are powers of the same prime. $\blacksquare$ This is a copy paste of the official solution. At least give credit ! see this
25.10.2021 20:54
Claim:- If $\gcd(m,n)=1$ then $$\sigma(mn)=\sigma(m)\sigma(n)$$ Proof:- Notice that $$\sigma(mn)=\left[\prod_{p_i|m} \frac{p_i^{\nu_p(m)}-1}{p_i-1} \right]\left[\prod_{p_i|n} \frac{p_i^{\nu_p(n)}-1}{p_i-1} \right]=\sigma(m)\sigma(n)$$Therefore we have $2$ cases:- Case 1:- $\gcd(m,n)=p^k x>1$ where $p \nmid x$ WLOG,rewrite $$m=p^R a \;\;\;\;\;\;\; n=p^j d$$Then the condition is equivalent to $$\left[ \frac{p^{R+j}-1}{p-1} \sigma(ad)-1 \right]\left[p^Rd-1 \right] =\left[\frac{p^R-1}{p-1} \sigma(d)-1\right] \left[p^{R+j} \sigma(ad)-1 \right]$$Looking $\pmod {p-1}$ we obtain by symmetry $a \equiv d \equiv 1 \pmod {p-1}$ However if $a,d>2(p-1)$ then $$\left[ \frac{p^{R+j}-1}{p-1} \sigma(ad)-1 \right]\left[p^Rd-1 \right]>\left[\frac{p^R-1}{p-1} \sigma(d)-1\right] \left[p^{R+j} \sigma(ad)-1 \right]$$i.e $a,d \in \{1,p\}$ or $(m,n)=(p^R,p^j)$ Case 2:- $\gcd(m,n)=1$ Then \begin{align*} \frac{mn-1}{n-1}=\frac{\sigma(m)\sigma(n)-1}{m-1} \;\;\;\; n>m \\ \text{ Let } x=\sigma(m) \;\;\;\;\;\;\;\; x \sigma(n)-1>(m+2)(x-1) \\ x(m-n)>m \end{align*}implying $$\frac{\sigma(m)-1}{m-1}<\frac{\sigma(mn)-1}{mn-1}$$,contradiction. Therefore $\boxed{(m,n)=(p^R,p^j)}$
07.03.2022 05:00
We claim that $\sigma(mn)\geq m\sigma(n)+\sigma(m)-m$. This is true since the right hand side counts the sum of all numbers that are either $m$ times a factor of $n$ or a factor of $m$ less than $m$. All of these numbers are factors of $mn$ and they are distinct. Therefore, we have \begin{align*} \frac{\sigma(mn)-1}{mn-1}&=\frac{m\sigma(n)+\sigma(m)-m-1}{mn-1}\\ &=\frac{m(\sigma(n)-1)+\sigma(m)-1}{mn-1}\\ &=\frac{(\sigma(n)-1)\left(m+\frac{m-1}{n-1}\right)}{mn-1}\\ &=\frac{(\sigma(n)-1)\left(\frac{mn-1}{n-1}\right)}{mn-1}\\ &=\frac{\sigma(n)-1}{n-1}. \end{align*} Therefore, equality must hold, which happens when $\sigma(mn)=m\sigma(n)+\sigma(m)-m$. Suppose that $p\mid n$ and $p$ is prime. Then, $p^{\nu_p(mn)}$ is a factor of $mn$. The equality can only be true if $p^{\nu_p(mn)}$ is $m$ times a factor of $n$ or a factor of $m$. If $p^{\nu_p(mn)}\mid m$, then $p^{\nu_p(n)}\mid\frac m{p^{\nu_p(m)}}$, which is impossible since the left side is a multiple of $p$ but the right side is not. Therefore, $p^{\nu_p(mn)}$ must be a multiple of $m$, so $m$ is a power of $p$. Suppose that there exists another prime $q$ such that $q\mid n$. Then, $m$ is also a power of $q$, which is a contradiction. Therefore, $m$ and $n$ must be powers of $p$. Now, we claim that $m=p^a$ and $n=p^b$ are solutions. We have $\sigma(p^n)-1=p\frac{p^n-1}{p-1}$, so $\frac{\sigma(p^n)-1}{p^n-1}=\frac p{p-1}$. Therefore, since $m$, $n$, and $mn$ are all powers of $p$, this means that all three numbers are equal to $\frac p{p-1}$, so the only solutions are $\boxed{(m,n)=(p^a,p^b)}$ where $a\geq b$ and $p$ is prime.
12.03.2022 06:05
don't know how to feel about this one Suppose $\gcd(m,n) = 1$. Then we have $\sigma(mn) = \sigma(m)\sigma(n)$. Let $t = \frac{\sigma(m)-1}{m-1}$, so $t(m-1)+1 = \sigma(m)$ and $t(n-1)+1=\sigma(n)$, implying that \[t(mn-1)+1 = \sigma(m)\sigma(n) = [t(m-1)+1][t(n-1)+1] = t^2(m-1)(n-1)+t[m+n-2]+1.\]This rearranges to $mn-1 = t(m-1)(n-1)+m+n-2$. That is, we have $(m-1)(n-1) = t(m-1)(n-1)$. But then $t=1$ and so $\sigma(m)=m$, which is absurd because $\sigma(m)\ge m+1$. Observe that the condition is equivalent to \[\frac{\sigma(mn)-\sigma(n)}{mn-n} = \frac{\sigma(mn)-\sigma(m)}{mn-m} = \frac{\sigma(mn)-1}{mn-1}\]by noting that $\frac ac = \frac bd$ when positive integers $a,b,c,d$ satisfy $a<b$ if and only if $\frac{b-a}{d-c} = \frac bd$. This directly implies $\sigma(mn)-\sigma(m) = m\sigma(n) - m$. That is, we have \[\sum_{d\mid mn, d\nmid m} d = m\sum_{c\mid n, c\ne 1}c.\]It is clear that the latter value is less than or equal to the first because every potential $mc$ would work as a value of $d$. Equality holds if there exist no $d\mid mn, d\nmid m$ with $m\nmid d$. As $\gcd(m,n)\ne 1$, there exists a prime $p\mid \gcd(m,n)$. We claim that $m$ is a perfect power of $p$ for any such $p$: otherwise, we can write $m = p^ek$ for some positive integers $e,k$ with $p\nmid k$ and $k\ge 2$, which means that $p^{e+1}$ is a value of $d$ contradicting the equality. Moreover, this implies $\gcd(m,n)$ has only one prime divisor, so $n$ is analogously a power of the same prime. Hence the only solutions could be prime powers $m=p^s,n=p^t$ with $n\ge t\ge 1$ and $p$ prime. All such solutions work, as for a given prime $p$ and exponent $z\ge 1$, we have \[\frac{\sigma(p^z)-1}{p^z-1} = \frac{\sum_{i=0}^z p^i - 1}{p^z-1} = \frac{1}{p-1}\cdot \frac{(p-1)\sum_{i=1}^z p^i}{p^z-1} = \frac{1}{p-1}\cdot \frac{p(p^z-1)}{p^z-1} = \frac{p}{p-1}.\]Thus we are done.
15.03.2023 22:07
First of all, we notice that the divisors of $mn$ contains - The divisors of $m$; - $m$ multiplied by the divisors of $n$, and that the intersection of both sets is $\{m\}$. Thus, summing over all elements, we have \[ \sigma(m)+m\sigma(n)-m \le \sigma(mn). \]However, we also have \[ \frac{\sigma(m)-1}{m-1}=\frac{m(\sigma(n)-1)}{m(n-1)} = \frac{\sigma(m)-1+m(\sigma(n)-1)}{m-1+m(n-1)}=\frac{\sigma(m)+m\sigma(n)-m}{mn-1} = \frac{\sigma(mn)-1}{mn-1}, \]so $\sigma(m)+m\sigma(n)-m = \sigma(mn)$. Hence, the set of the divisors of $mn$ is exactly the union of the set of the divisors $m$ and $m$ multiplied by the set of the divisors of $n$, with an intersection of $m$. Counting these divisors, we obtain $d(mn)=d(m)+d(n)-1$. Let $A$ be the set of logarithms of the divisors of $m$, and $B$ be the set of logarithms of the divisors of $n$. Then, $|A+B|=|A|+|B|-1$, which is the equality case of the Cauchy-Davenport inequality, and therefore $A$ and $B$ have all elements in arithmetic progression when written in increasing order, so $m$ and $n$ are prime powers. However, note that for prime $p$ and nonnegative $e$, \[ \frac{\sigma(p^e)-1}{p^e-1}=\frac{p}{p-1}, \]so $m$ and $n$ must be powers of the same prime. Since all such solutions $(m, n)$ can be verified to work, the final answer is all $m, n$ with $m=p^a$ and $n=p^b$ where $a \ge b > 0$ and $p$ is any prime.
05.10.2023 04:35
The answer is $(m,n)=(p^a,p^b)$ with $a \geq b$ and $p$ prime. These work, since for any $k$ we have $$\frac{\sigma(p^k)-1}{p^k-1}=\frac{p^k+\cdots+p}{p^k-1}=\frac{p\cdot \frac{p^k-1}{p-1}}{p^k-1}=\frac{p}{p-1}.$$I now show that these are the only solutions. The key claim is the following. Claim: In general, we have $\sigma(mn) \geq m\sigma(n)+\sigma(m)-m$. Proof: Observe that the LHS counts the sum of the proper divisors of $m$, as well as $m$ times the divisors of $n$. All of these are divisors of $mn$, and they are distinct for size reasons. $\blacksquare$ Note that equality only holds if the set of divisors of $mn$ is precisely the union of the proper divisors of $m$ and $m$ times the divisors of $n$. This clearly implies that no primes not dividing $m$ can divide $n$, since if $q$ is such a prime then $q$ is a divisor of $mn$ but is not a proper divisor of $m$, nor can it be divisible by $m$. On the other hand, if we have two primes $p,q$ dividing $m$ with $p \mid n$, then $p^{\nu_p(m)+1}$ is a divisor of $mn$, but not a divisor of $m$ nor divisible by $m$. Thus $m$ is a prime power, hence $n$ is a power of the same prime. Now we perform algebraic manipulations. $$\frac{\sigma(mn)-1}{mn-1}=\frac{\sigma(m)-1}{m-1}=\frac{m\sigma(n)-m}{mn-m}=\frac{m\sigma(n)-m+\sigma(m)-1}{mn-m+m-1}=\frac{m\sigma(n)+\sigma(m)-m-1}{mn-1},$$hence we require $\sigma(mn)=m\sigma(n)+\sigma(m)-m$. Thus $m,n$ must be powers of the same prime. $\blacksquare$
15.10.2023 22:07
I actually think this was a pretty easy problem for a P8. Every step was motivated and not too long of a solution.
In particular, m,n are prime powers, as desired.
24.08.2024 02:41
This is one of those ``solution comes out of nowhere" problems where you have to do the algebraic manipulation and somehow notice that you're just done without thinking too much beforehand. The answer is $(p^a, p^b)$ for $a \geq b$, which work. Observe that \[\frac{\sigma(m)-1}{m-1} = \frac{\sigma(n) - 1}{n-1} = \frac{m\sigma(n) + \sigma(m) - m-1}{mn-1}\]in other words $\sigma(mn) = m\sigma(n) + \sigma(m) - m$. The key now is that $m\sigma(n)$ is a copy of the divisors from $n$ (because $m>n$), so all the divisors of $mn$ are given by \[D_{mn} = \{1, e_2, e_3, \dots, e_{\ell - 1}, m, md_2, md_3, \dots, md_{k-1}, mn\}\]where the $e_i$ are divisors of $m$ and $d_i$ are divisors of $n$. In particular, the $d_i$ are a subset of the $e_i$, so $n \mid m$. Now $\gcd(m, n) > 1$, so take some prime $p \mid m$ that also divides $n$. Say that $\nu_p(m) = k$; then $p^{k+1}$ divides $mn$, hence it is one of the $md_i$, hence $m$ is a prime power and it follows $n$ must also be a prime power, as needed.