Library / Berkeley Math Circle /60 of 98

Berkeley Math Circle

Number theory Difficulty 5.0 AIME, harder Prove it United States

Problem:

Does there exist a function $f$ from the positive integers to itself, such that for any positive integers $a$ and $b$ , we have $\operatorname{gcd}(a, b)=1$ if and only if $\operatorname{gcd}(f(a), f(b))>1$ holds?

Solution

Solution:

The answer is no. Assume that $f$ satisfies the hypothesis. Let $k$ denote the number of distinct primes dividing $f(1)$ . For every integer $e$ , the number $f\left(2^{e}\right)$ shares some prime factor with $f(1)$ . So among $f(2), f(4), \ldots, f\left(2^{k+1}\right)$ two of them have the same shared prime factor, which is impossible.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.