Maths Olympiad Prep

Library / /3 of 30

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Germany

Problem:
Find all pairs (a,b)(a, b) of positive integers for which there exists a positive integer nn such that the number of divisors of nan a and nbn b is identical.

Solution

Solution:
The pairs sought are those for which one of the three conditions a=b,aba=b, a \nmid b or bab \nmid a is satisfied, i.e., all pairs of positive integers except those for which one of the numbers a,ba, b is a proper divisor of the other.
Throughout the entire proof we will denote the number of all divisors of a positive integer mm by τ(m)\tau(m). First it is clear that in the case a=ba=b one can choose an arbitrary nn. Furthermore, in the case that aa is a proper divisor of bb, for every positive integer nn the number nan a is a proper divisor of nbn b, so the set of its divisors is a proper subset of the set of divisors of nbn b, which implies τ(na)<τ(nb)\tau(n a)<\tau(n b). The case ba,b<ab \mid a, b<a is treated analogously.
It remains to show that in the case ab,baa \nmid b, b \nmid a we can always find an nn with τ(na)=τ(nb)\tau(n a)=\tau(n b). For this we first prove the following statement.
Lemma. Let α>β\alpha>\beta be positive integers. Then for every integer M>βM>\beta there exists a positive integer γ\gamma such that
α+γ+1β+γ+1=1+1M=M+1M. \frac{\alpha+\gamma+1}{\beta+\gamma+1}=1+\frac{1}{M}=\frac{M+1}{M} .
Proof. Rearranging the first equation gives γ=M(αβ)(β+1)0\gamma=M(\alpha-\beta)-(\beta+1) \geq 0. Now we consider the prime factorization a=ppαpa=\prod_{p} p^{\alpha_{p}} and b=ppβpb=\prod_{p} p^{\beta_{p}} of aa and bb. Let p1,pkp_{1}, \ldots p_{k} now be all those primes pp with αp>βp\alpha_{p}>\beta_{p} and q1,,qq_{1}, \ldots, q_{\ell} all primes qq with αq<βq\alpha_{q}<\beta_{q}. Since ab,baa \nmid b, b \nmid a, both kk and \ell are positive. Let XX now be a positive integer that is greater than all αp\alpha_{p} and βb\beta_{b}. By the lemma above we can then choose numbers γ1,,γk\gamma_{1}, \ldots, \gamma_{k} and γ1,,γ\gamma_{1}^{\prime}, \ldots, \gamma_{\ell}^{\prime} such that
αpi+γi+1βpi+γi+1=kX+ikX+i1, and αqj+γj+1βqj+γj+1=X+j1X+j \frac{\alpha_{p_{i}}+\gamma_{i}+1}{\beta_{p_{i}}+\gamma_{i}+1}=\frac{k X+i}{k X+i-1}, \quad \text{ and } \quad \frac{\alpha_{q_{j}}+\gamma_{j}^{\prime}+1}{\beta_{q_{j}}+\gamma_{j}^{\prime}+1}=\frac{\ell X+j-1}{\ell X+j}
holds for all 1ik1 \leq i \leq k and 1j1 \leq j \leq \ell. For n=(i=1kpiγi)(j=1qjγj)n=\left(\prod_{i=1}^{k} p_{i}^{\gamma_{i}}\right) \cdot\left(\prod_{j=1}^{\ell} q_{j}^{\gamma_{j}^{\prime}}\right) it now follows, using the well-known formula
τ(ppηp)=p(ηp+1) \tau\left(\prod_{p} p^{\eta_{p}}\right)=\prod_{p}\left(\eta_{p}+1\right)
that
τ(na)τ(nb)=(i=1kαpi+γi+1βpi+γi+1)(j=1αqj+γj+1βqj+γj+1)=k(X+1)kXX(X+1)=1 \frac{\tau(n a)}{\tau(n b)}=\left(\prod_{i=1}^{k} \frac{\alpha_{p_{i}}+\gamma_{i}+1}{\beta_{p_{i}}+\gamma_{i}+1}\right) \cdot\left(\prod_{j=1}^{\ell} \frac{\alpha_{q_{j}}+\gamma_{j}^{\prime}+1}{\beta_{q_{j}}+\gamma_{j}^{\prime}+1}\right)=\frac{k(X+1)}{k X} \cdot \frac{\ell X}{\ell(X+1)}=1
so nn is as claimed.

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 translated into English from de; metadata (topic, difficulty) added by this project.