25th Turkish Mathematical Olympiad

Question

For each positive integer n let d(n) be the number of prime divisors of n. Show that for each positive integer n there are positive integers k, m satisfying k - m = n and d(k) - d(m) = 1.

Accepted Answer

Let p be the smallest prime not dividing n. Then all prime divisors of p-1 divide n and d((p-1)n) = d(n). Now note that k = pn and m = (p-1)n satisfy the conditions. Indeed, k - m = n and d(k) - d(m) = d(pn) - d((p-1)n) = (d(n) + 1) - d(n) = 1.