Maths Olympiad Prep

Library / /4 of 22

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

Find all positive integers kk such that
m+nm2kmn+n2 \frac{m+n}{m^2-kmn+n^2}
is not a composite number for any positive integers mm and nn. (Borna Vukorepa)

Solution

Considering a fixed positive integer kk with the given property, by plugging (m,n)(k,1)(m, n) \leftarrow (k, 1) and (m,n)(k2+k1,k+1)(m, n) \leftarrow (k^2 + k - 1, k + 1) we find that both
k+1k2k2+1=k+1 \frac{k+1}{k^2 - k^2 + 1} = k + 1
and
(k2+k1)+(k+1)(k2+k1)2k(k2+k1)(k+1)+(k+1)2=k2+2kk+2=k \frac{(k^2 + k - 1) + (k + 1)}{(k^2 + k - 1)^2 - k(k^2 + k - 1)(k + 1) + (k + 1)^2} = \frac{k^2 + 2k}{k + 2} = k
are not composite. Since they are of different parity, it follows that k=1k = 1 or k=2k = 2.

1) If k=1k = 1, then m+nm2mn+n22\frac{m+n}{m^2-mn+n^2} \le 2, satisfying the conditions of the problem. Indeed,
m+nm2mn+n22    (mn)2+m(m1)+n(n1)0. \frac{m+n}{m^2-mn+n^2} \le 2 \iff (m-n)^2 + m(m-1) + n(n-1) \ge 0.

2) k=2k = 2 does not satisfy the conditions of the problem. For example, plugging (m,n)(5,4)(m, n) \leftarrow (5, 4) into m+nm22mn+n2=m+n(mn)2\frac{m+n}{m^2-2mn+n^2} = \frac{m+n}{(m-n)^2} yields composite number 9.

Therefore, k=1k = 1 is the only positive integer with the given property.

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.