Maths Olympiad Prep

Library / /68 of 155

Number theory Difficulty 5.9 AIME, harder Prove it Saudi Arabia

A positive integer k>1k>1 is called nice if for any pair (m,nm, n) of positive integers satisfying the condition kn+mkm+nk n + m \mid k m + n we have nmn \mid m.
1. Prove that 55 is a nice number;
2. Find all nice numbers.

Solution

1) For k=5k=5, we need to prove that for all m,nm, n satisfying 5n+m5m+n5 n + m \mid 5 m + n then nmn \mid m. Note that 5n+m5m+n5 n + m \leq 5 m + n or nmn \leq m, then 15m+n5n+m<51 \leq \frac{5 m + n}{5 n + m} < 5.

Then A=5m+n5n+m{1,2,3,4}A = \frac{5 m + n}{5 n + m} \in \{1, 2, 3, 4\}. We consider some cases:

- If A=1A = 1 then m=nm = n.
- If A=2A = 2 then 5m+n=10n+2mm=3n5 m + n = 10 n + 2 m \Leftrightarrow m = 3 n.
- If A=3A = 3 then 5m+n=15n+3mm=7n5 m + n = 15 n + 3 m \Leftrightarrow m = 7 n.
- If A=4A = 4 then 5m+n=20n+4mm=19n5 m + n = 20 n + 4 m \Leftrightarrow m = 19 n.

So in all cases, we always have nmn \mid m, which implies that k=5k = 5 is a nice number.

2) We can directly check that k=2k = 2 is a nice number. Consider some nice number k>2k > 2. By a similar way, we can check that nmn \leq m and
1km+nkn+m<k. 1 \leq \frac{k m + n}{k n + m} < k.
Thus A=km+nkn+m{1,2,3,,k1}A = \frac{k m + n}{k n + m} \in \{1, 2, 3, \ldots, k-1\}. In case A=2A = 2, we have
km+nkn+m=2km+n=2m+2knmn=2k1k2. \frac{k m + n}{k n + m} = 2 \Leftrightarrow k m + n = 2 m + 2 k n \Leftrightarrow \frac{m}{n} = \frac{2k - 1}{k - 2}.
We must have mnZ+\frac{m}{n} \in \mathbb{Z}^+ then 2k1k2=2+3k2Z+\frac{2k - 1}{k - 2} = 2 + \frac{3}{k - 2} \in \mathbb{Z}^+. Since k>1k > 1, this means that k2{1,3}k - 2 \in \{1, 3\} or k{3,5}k \in \{3, 5\}.

It is easy to check that k=3k = 3 is also a nice number. Therefore, all nice numbers are 2,3,52, 3, 5.

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.