Maths Olympiad Prep

Library / /39 of 48

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

Find all integers nn satisfying n2n \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α1pkα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
pk1=σ(n)n=i=1k(1+1pi++1piαi)<i=1k111pi=i=1k(1+1pi1)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, pk1<k+1p_{k}-1<k+1, which is impossible for k3k \geq 3, because in this case pk12k2k+1p_{k}-1 \geq 2 k-2 \geq k+1. Then k2k \leq 2 and pk<k+24p_{k}<k+2 \leq 4, which implies pk3p_{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α+11)(3β+11)2^{\alpha+2} 3^{\beta}=\left(2^{\alpha+1}-1\right)\left(3^{\beta+1}-1\right). Since 2α+112^{\alpha+1}-1 is not divisible by 22, and 3β+113^{\beta+1}-1 is not divisible by 33, we have
{2α+11=3β3β+11=2α+2{2α+11=3β3(2α+11)1=22α+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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.