Competition problem — Number theory

Library / /70 of 128

Number theory Difficulty 5.4 AIME, harder Prove it Philippines

Problem:

How many pairs of positive integers $(a, b)$ are there, both not exceeding $10$ , such that $a \leq \operatorname{gcd}(a, b) \leq b$ and $a \leq \operatorname{lcm}(a, b) \leq b$ ?

Solution

Solution:

$\operatorname{gcd}(a, b) \geq a \Longrightarrow \operatorname{gcd}(a, b) = a$ . Likewise, $\operatorname{lcm}(a, b) = b$ . This can only happen if $b$ is a multiple of $a$ . Hence the answer is $10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 27$ .

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.