Maths Olympiad Prep

Library / /693 of 740

, 2024

Number theory Difficulty 5.7 AIME, harder Prove it United States

Problem:

For all positive integers rr and ss, let Top(r,s)\operatorname{Top}(r, s) denote the top number (i.e., numerator) when rs\frac{r}{s} is written in simplified form. For instance, Top(20,24)=5\operatorname{Top}(20,24)=5. Compute the number of ordered pairs of positive integers (a,z)(a, z) such that 200a300200 \leq a \leq 300 and Top(a,z)=Top(z,a1)\operatorname{Top}(a, z)=\operatorname{Top}(z, a-1).

Solution

Solution:

In general, Top(r,s)=rgcd(r,s)\operatorname{Top}(r, s)=\frac{r}{\operatorname{gcd}(r, s)}. We characterize all possible (a,z)(a, z) as follows.

Claim 1. For any positive integers aa and zz, we have Top(a,z)=Top(z,a1)\operatorname{Top}(a, z)=\operatorname{Top}(z, a-1) if and only if there exists positive integers dd and ee such that ed21e \mid d^{2}-1, a=d2a=d^{2}, and z=dez=d e.

Proof. ()(\Leftarrow) From ed21e \mid d^{2}-1, we deduce that gcd(d,e)=1\operatorname{gcd}(d, e)=1. Thus, Top(a,z)=d2gcd(d2,de)=d2d=d\operatorname{Top}(a, z)=\frac{d^{2}}{\operatorname{gcd}\left(d^{2}, d e\right)}=\frac{d^{2}}{d}=d. We also have gcd(z,a1)=gcd(de,d21)=e\operatorname{gcd}(z, a-1)=\operatorname{gcd}\left(d e, d^{2}-1\right)=e, so Top(z,a1)=dee=d\operatorname{Top}(z, a-1)=\frac{d e}{e}=d as well.

()(\Rightarrow) Let d=gcd(a,z)d=\operatorname{gcd}(a, z) and e=gcd(z,a1)e=\operatorname{gcd}(z, a-1). We have that gcd(d,e)=1\operatorname{gcd}(d, e)=1 because it divides both aa and a1a-1. The equation implies that ad=ze\frac{a}{d}=\frac{z}{e}, or az=de\frac{a}{z}=\frac{d}{e}. The left side has simplified form a/dz/d\frac{a / d}{z / d}, and the right side is already simplified. Thus, a=d2a=d^{2} and z=dez=d e. Finally, e=gcd(z,a1)a1=d21e=\operatorname{gcd}(z, a-1) \mid a-1=d^{2}-1.

The condition that 200a300200 \leq a \leq 300 implies d{15,16,17}d \in\{15,16,17\}. Once we select dd, each divisor ee of d21d^{2}-1 yields a solution. Thus, the answer is
τ(1521)+τ(1621)+τ(1721)=τ(1416)+τ(1517)+τ(1618)=12+8+18=38 \begin{aligned} \tau\left(15^{2}-1\right)+\tau\left(16^{2}-1\right)+\tau\left(17^{2}-1\right) & =\tau(14 \cdot 16)+\tau(15 \cdot 17)+\tau(16 \cdot 18) \\ & =12+8+18=38 \end{aligned}
where τ(n)\tau(n) is the number of divisors of nn.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.