Track / Stage 5 / 12 of 400 #612 of 2000

Problem 612

AIME late

Number theory Difficulty 5.0 Prove it Berkeley Math Circle · 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?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.