, 2010

Note at first that $da \ominus db = a \ominus b$ for all positive integers $a, b$, and $d$. Indeed,
$$da \ominus db = \frac{da - db}{\text{gcd}(da, db)} = \frac{d \cdot (a-b)}{d \cdot \text{gcd}(a,b)} = \frac{a-b}{\text{gcd}(a,b)} = a \ominus b.$$
Show now that if $n$ is a prime power and $m < n$, then $n \ominus m$ is relatively prime to $n$. Indeed, let $n = p^k$ where $p$ is a prime number, and let $m = p^i s$ where $\text{gcd}(p, s) = 1$. Then $m < n$ implies $i < k$. Now
$$n \ominus m = p^{k-i} \ominus s = \frac{p^{k-i} - s}{\text{gcd}(p^{k-i}, s)} = p^{k-i} - s$$
because $\text{gcd}(p^{k-i}, s) = 1$ by the choice of $s$. Also, for the same reason, $\text{gcd}(p, p^{k-i} - s) = 1$, hence $\text{gcd}(n, n \ominus m) = \text{gcd}(p^k, p^{k-i} - s) = 1$.
It remains to show that if $n$ is not a prime power, then there exists a positive integer $m$ such that $m < n$ and the integers $n \ominus m$ and $n$ share a common prime factor. Since $n$ is not a prime power, it has at least two different prime factors. Let $p$ and $q$ be some prime factors of $n$, whereby $p < q$. Let $n = p^k t$ where $\text{gcd}(p, t) = 1$. Take $m = n - p^{k+1}$. As $n$ is divisible by both $p^k$ and $q$ which are relatively prime, it is also divisible by their product $p^k q$. Consequently, $p^{k+1} < p^k q \le n$, i.e., $0 < m < n$. Now
$$n \ominus m = n \ominus (n - p^{k+1}) = t \ominus (t - p) = \frac{t - (t-p)}{\text{gcd}(t, t-p)} = \frac{p}{\text{gcd}(t, p)} = p$$
since $\text{gcd}(t, p) = 1$. We see that $n \ominus m$ and $n$ have a common prime factor $p$.