Maths Olympiad Prep

Library / /108 of 155

Number theory Difficulty 6.5 National olympiad Prove it Saudi Arabia

Find all pair of integers (mm, nn) and mnm \geq n such that there exist a positive integer ss and
1. Product of all divisors of sms m, sns n are equal.
2. Number of divisors of sms m, sns n are equal.

Solution

1) Denote d(x)d(x), π(x)\pi(x) as the number of divisors, the product of divisors of positive integer xx.
Firstly, we can see that for any divisor yky_{k} of xx, 1kd(x)1 \leq k \leq d(x) then xyi\frac{x}{y_{i}} is also divisor of xx, thus
k=1d(x)yk=k=1d(x)xyk so (k=1d(x)yk)2=xd(x), hence π(x)=xd(x)2 \prod_{k=1}^{d(x)} y_{k} = \prod_{k=1}^{d(x)} \frac{x}{y_{k}} \text{ so } \left(\prod_{k=1}^{d(x)} y_{k}\right)^{2} = x^{d(x)}, \text{ hence } \pi(x) = x^{\frac{d(x)}{2}}
Thus for any m,nZ+m, n \in \mathbb{Z}^{+} then π(m)=π(n)\pi(m) = \pi(n) implies that m,nm, n share the common prime divisors set SS.
Suppose that d(m)d(n)d(m) \geq d(n) and take pSp \in S. Since md(m)=nd(n)m^{d(m)} = n^{d(n)}, we have d(m)vp(m)=d(n)vp(n)d(m) \cdot v_{p}(m) = d(n) \cdot v_{p}(n). Since d(m)d(n)d(m) \geq d(n), we get vp(m)vp(n)v_{p}(m) \leq v_{p}(n). And this is true for all pSp \in S, thus
d(m)=pS(vp(m)+1)pS(vp(n)+1)=d(n) d(m) = \prod_{p \in S} (v_{p}(m) + 1) \leq \prod_{p \in S} (v_{p}(n) + 1) = d(n)
So d(m)=d(n)d(m) = d(n), which implies that m=nm = n. Therefore, we can find a positive integer such that product of all divisors of sms m, sns n are equal if and only if m=nm = n.

2) Firstly, we can see that if nmn \mid m then any divisor of sns n is also divisor of sms m, so d(sn)<d(sm)d(s n) < d(s m). We consider nmn \nmid m, and denote p1,p2,,ptp_{1}, p_{2}, \ldots, p_{t} be all prime dividing mnm n. Suppose that
m=i=1tpiαi and n=i=1tpiβi m = \prod_{i=1}^{t} p_{i}^{\alpha_{i}} \text{ and } n = \prod_{i=1}^{t} p_{i}^{\beta_{i}}
Now we are looking for s=i=1tpiγis = \prod_{i=1}^{t} p_{i}^{\gamma_{i}} such that
d(sm)d(sn)=i=1tαi+γi+1βi+γi+1=1 \frac{d(s m)}{d(s n)} = \prod_{i=1}^{t} \frac{\alpha_{i} + \gamma_{i} + 1}{\beta_{i} + \gamma_{i} + 1} = 1
Note that if αi=βi\alpha_{i} = \beta_{i}, then regardless of the value of γi\gamma_{i}, the corresponding factor equals to 1 and does not affect the product. So we may assume that αiβi\alpha_{i} \neq \beta_{i} for all 1it1 \leq i \leq t.

Claim. Let α>β\alpha > \beta be nonnegative integers. Then for every Mβ+1M \geq \beta + 1, there exist a nonnegative integer γ\gamma such that
α+γ+1β+γ+1=M+1M. \frac{\alpha + \gamma + 1}{\beta + \gamma + 1} = \frac{M + 1}{M} .
It is equivalent to γ=M(αβ)(β+1)0\gamma = M(\alpha - \beta) - (\beta + 1) \geq 0, which is true.

Back to the original problem, we can assume that αi>βi\alpha_{i} > \beta_{i} for i=1,2,,ui = 1, 2, \ldots, u and αi<βi\alpha_{i} < \beta_{i} for i=u+1,u+2,,ti = u + 1, u + 2, \ldots, t. Take some big enough XX and choose γi\gamma_{i} such that
- αi+γi+1βi+γi+1=uX+iuX+i1\frac{\alpha_{i} + \gamma_{i} + 1}{\beta_{i} + \gamma_{i} + 1} = \frac{u X + i}{u X + i - 1} for 1iu1 \leq i \leq u.
- βu+i+γu+i+1αu+i+γu+i+1=(tu)X+i(tu)X+i1\frac{\beta_{u + i} + \gamma_{u + i} + 1}{\alpha_{u + i} + \gamma_{u + i} + 1} = \frac{(t - u) X + i}{(t - u) X + i - 1} for 1itu1 \leq i \leq t - u.
Then we have
d(sm)d(sn)=i=1uuX+iuX+i1i=1tu(tu)X+i1(tu)X+i=u(X+1)uX(tu)X(tu)(X+1)=1. \frac{d(s m)}{d(s n)} = \prod_{i=1}^{u} \frac{u X + i}{u X + i - 1} \cdot \prod_{i=1}^{t - u} \frac{(t - u) X + i - 1}{(t - u) X + i} = \frac{u(X + 1)}{u X} \cdot \frac{(t - u) X}{(t - u)(X + 1)} = 1 .

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.