Maths Olympiad Prep

Library / /9 of 17

, 2007

Number theory Difficulty 6.0 AIME, harder Prove it Japan

Find all positive integer pairs (m,n)(m, n) that satisfy the following conditions.
(1) m,n20 (1)\ m, n \leq 20
(2) mm and nn are relatively prime.
(3)57<mn<34 (3) \quad \frac{5}{7} < \frac{m}{n} < \frac{3}{4}

Solution

Now put p=nmp = n - m, q=nq = n. Finding all positive integer pairs (m,n)(m, n) is equivalent to finding all integer pairs (p,q)(p, q). And then condition (1) and (3) is equivalent to the conditions that 1q201 \leq q \leq 20, 14<pq<27\frac{1}{4} < \frac{p}{q} < \frac{2}{7}. And condition (2) is equivalent to the condition that pp and qq are relatively prime. And 14<pq<27\frac{1}{4} < \frac{p}{q} < \frac{2}{7} is equivalent to 72p<q<4p\frac{7}{2}p < q < 4p. So,
* If p0p \leq 0, qq doesn't exist because of pq0\frac{p}{q} \leq 0
* If p=1p = 1, then 72<q<4\frac{7}{2} < q < 4, so qq doesn't exist.
* If p=2p = 2, then 7<q<87 < q < 8, so qq doesn't exist.
* If p=3p = 3, then 212<q<12\frac{21}{2} < q < 12, so q=11q = 11.
* If p=4p = 4, then 14<q<1614 < q < 16, so q=15q = 15.
* If p=5p = 5, then 352<q<20\frac{35}{2} < q < 20, so q=18,19q = 18, 19.
* If p6p \geq 6, qq doesn't exist because q>72p21q > \frac{7}{2}p \geq 21.
Then all integer pairs (p,q)(p, q) are (3,11)(3, 11), (4,15)(4, 15), (5,18)(5, 18), (5,19)(5, 19). So, all positive integer pairs (m,n)(m, n) are (13,18)(13, 18), (8,11)(8, 11), (11,15)(11, 15), (14,19)(14, 19).

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.