Maths Olympiad Prep

Library / Asian Pacific Mathematics Olympiad /46 of 55

Asian Pacific Mathematics Olympiad

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Find all integers nn satisfying n≥2n \geq 2 and σ(n)p(n)−1=n\frac{\sigma(n)}{p(n)-1}=n, in which σ(n)\sigma(n) denotes the sum of all positive divisors of nn, and p(n)p(n) denotes the largest prime divisor of nn.

Solution

Let n=p1α1⋅…⋅pkαkn=p_{1}^{\alpha_{1}} \cdot \ldots \cdot p_{k}^{\alpha_{k}} be the prime factorization of nn with p1<…<pkp_{1}<\ldots<p_{k}, so that p(n)=pkp(n)=p_{k} and σ(n)=(1+p1+⋯+p1α1)…(1+pk+⋯+pkαk)\sigma(n)=\left(1+p_{1}+\cdots+p_{1}^{\alpha_{1}}\right) \ldots\left(1+p_{k}+\cdots+p_{k}^{\alpha_{k}}\right). Hence
pk−1=σ(n)n=∏i=1k(1+1pi+⋯+1piαi)<∏i=1k11−1pi=∏i=1k(1+1pi−1)≤∏i=1k(1+1i)=k+1p_{k}-1=\frac{\sigma(n)}{n}=\prod_{i=1}^{k}\left(1+\frac{1}{p_{i}}+\cdots+\frac{1}{p_{i}^{\alpha_{i}}}\right)<\prod_{i=1}^{k} \frac{1}{1-\frac{1}{p_{i}}}=\prod_{i=1}^{k}\left(1+\frac{1}{p_{i}-1}\right) \leq \prod_{i=1}^{k}\left(1+\frac{1}{i}\right)=k+1,
that is, pk−1<k+1p_{k}-1<k+1, which is impossible for k≥3k \geq 3, because in this case pk−1≥2k−2≥k+1p_{k}-1 \geq 2 k-2 \geq k+1. Then k≤2k \leq 2 and pk<k+2≤4p_{k}<k+2 \leq 4, which implies pk≤3p_{k} \leq 3.
If k=1k=1 then n=pαn=p^{\alpha} and σ(n)=1+p+⋯+pα\sigma(n)=1+p+\cdots+p^{\alpha}, and in this case n∤σ(n)n \nmid \sigma(n), which is not possible. Thus k=2k=2, and n=2α3βn=2^{\alpha} 3^{\beta} with α,β>0\alpha, \beta>0. If α>1\alpha>1 or β>1\beta>1,
σ(n)n>(1+12)(1+13)=2. \frac{\sigma(n)}{n}>\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)=2 .
Therefore α=β=1\alpha=\beta=1 and the only answer is n=6n=6.

Comment: There are other ways to deal with the case n=2α3βn=2^{\alpha} 3^{\beta}. For instance, we have 2α+23β=(2α+1−1)(3β+1−1)2^{\alpha+2} 3^{\beta}=\left(2^{\alpha+1}-1\right)\left(3^{\beta+1}-1\right). Since 2α+1−12^{\alpha+1}-1 is not divisible by 22, and 3β+1−13^{\beta+1}-1 is not divisible by 33, we have
{2α+1−1=3β3β+1−1=2α+2⟺{2α+1−1=3β3⋅(2α+1−1)−1=2⋅2α+1⟺{2α+1=43β=3, \left\{\begin{array} { l } { 2 ^ { \alpha + 1 } - 1 = 3 ^ { \beta } } \\ { 3 ^ { \beta + 1 } - 1 = 2 ^ { \alpha + 2 } } \end{array} \Longleftrightarrow \left\{\begin{array} { c } { 2 ^ { \alpha + 1 } - 1 = 3 ^ { \beta } } \\ { 3 \cdot ( 2 ^ { \alpha + 1 } - 1 ) - 1 = 2 \cdot 2 ^ { \alpha + 1 } } \end{array} \Longleftrightarrow \left\{\begin{array}{r} 2^{\alpha+1}=4 \\ 3^{\beta}=3 \end{array},\right.\right.\right.
and n=2α3β=6n=2^{\alpha} 3^{\beta}=6.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.