Maths Olympiad Prep

Library / /63 of 156

Number theory Difficulty 4.6 AIME Find the answer China

Given rational number r=pq(0,1)r = \frac{p}{q} \in (0, 1), pp, qq are coprime positive integers, and pqpq divides 36003600. The number of such rational numbers rr is ______.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Suppose set Ω={rr=pq, p,qN+, (p,q)=1, pq3600}\Omega = \{ r \mid r = \frac{p}{q},\ p, q \in \mathbb{N}_+,\ (p, q) = 1,\ pq \mid 3600 \}.
We consider the reduced fractional form pq\frac{p}{q} of any element rr of Ω\Omega. Since the standard factorization of 36003600 is 24×32×522^4 \times 3^2 \times 5^2, we can set p=2A×3B×5Cp = 2^A \times 3^B \times 5^C, q=2a×3b×5cq = 2^a \times 3^b \times 5^c, where min{A,a}=min{B,b}=min{C,c}=0\min\{A, a\} = \min\{B, b\} = \min\{C, c\} = 0 and A+a4A + a \le 4, B+b2B + b \le 2, C+c2C + c \le 2.
Therefore, there are 99 ways to take such number pair (A,a)(A, a), 55 ways to take number pair (B,b)(B, b), and 55 ways to take number pair (C,c)(C, c).
As a result, the number of the elements of Ω\Omega is Ω=9×5×5=225|\Omega| = 9 \times 5 \times 5 = 225.
All the rational numbers satisfying the conditions are Ω(0,1)\Omega \cap (0, 1). Notice that rΩr \in \Omega if and only if 1rΩ\frac{1}{r} \in \Omega. In particular, 1Ω1 \in \Omega. Therefore, the elements in Ω{1}\Omega \setminus \{1\} can be matched into
12(Ω1)=112 \frac{1}{2}(|\Omega| - 1) = 112
pairs according to the product of 11, and each pair has exactly one number belonging to (0,1)(0, 1), that is, there is exactly one number satisfying the conditions. Thus, the number of desired rational numbers rr is 112112. \square

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.