Number theoryDifficulty 6.5National olympiadProve itSaudi Arabia
Find all pair of integers (m, n) and m≥n such that there exist a positive integer s and 1. Product of all divisors of sm, sn are equal. 2. Number of divisors of sm, sn are equal.
Solution
1) Denote d(x), π(x) as the number of divisors, the product of divisors of positive integer x. Firstly, we can see that for any divisor yk of x, 1≤k≤d(x) then yix is also divisor of x, thus k=1∏d(x)yk=k=1∏d(x)ykx so k=1∏d(x)yk2=xd(x), hence π(x)=x2d(x) Thus for any m,n∈Z+ then π(m)=π(n) implies that m,n share the common prime divisors set S. Suppose that d(m)≥d(n) and take p∈S. Since md(m)=nd(n), we have d(m)⋅vp(m)=d(n)⋅vp(n). Since d(m)≥d(n), we get vp(m)≤vp(n). And this is true for all p∈S, thus d(m)=p∈S∏(vp(m)+1)≤p∈S∏(vp(n)+1)=d(n) So d(m)=d(n), which implies that m=n. Therefore, we can find a positive integer such that product of all divisors of sm, sn are equal if and only if m=n.
2) Firstly, we can see that if n∣m then any divisor of sn is also divisor of sm, so d(sn)<d(sm). We consider n∤m, and denote p1,p2,…,pt be all prime dividing mn. Suppose that m=i=1∏tpiαi and n=i=1∏tpiβi Now we are looking for s=∏i=1tpiγi such that d(sn)d(sm)=i=1∏tβi+γi+1αi+γi+1=1 Note that if αi=βi, then regardless of the value of γi, the corresponding factor equals to 1 and does not affect the product. So we may assume that αi=βi for all 1≤i≤t.
Claim. Let α>β be nonnegative integers. Then for every M≥β+1, there exist a nonnegative integer γ such that β+γ+1α+γ+1=MM+1. It is equivalent to γ=M(α−β)−(β+1)≥0, which is true.
Back to the original problem, we can assume that αi>βi for i=1,2,…,u and αi<βi for i=u+1,u+2,…,t. Take some big enough X and choose γi such that - βi+γi+1αi+γi+1=uX+i−1uX+i for 1≤i≤u. - αu+i+γu+i+1βu+i+γu+i+1=(t−u)X+i−1(t−u)X+i for 1≤i≤t−u. Then we have d(sn)d(sm)=i=1∏uuX+i−1uX+i⋅i=1∏t−u(t−u)X+i(t−u)X+i−1=uXu(X+1)⋅(t−u)(X+1)(t−u)X=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.