Question 89
Let $\mathbb{N}$ denote the set of all positive integers and $\mathbb{N}^2$ the set of ordered pairs of positive integers. Among all functions from $\mathbb{N}^2$ to $\mathbb{N}$, we define recursively, for every non-negative integer $k$, the good functions of order $k$ as follows:
(i) The functions $f(a,b) = a$ and $f(a,b) = b$ are good functions of order $0$.
(ii) If $f(a,b)$ and $g(a,b)$ are good functions of orders $p$ and $q$ respectively, then $\text{gcd}(f(a,b), g(a,b))$ is a good function of order $p+q$, and $f(a,b)g(a,b)$ is a good function of order $p+q+1$.
Prove that if, for some positive integer $n \ge 3$, $f(a,b)$ is a good function of order $k$ with $k \le C_3^n$, then there exist a positive integer $t \le C_2^n$ and $t$ pairs of non-negative integers $(x_1, y_1), \dots, (x_t, y_t)$ such that
$$
f(a,b) = \text{gcd}(a^{x_1}b^{y_1}, \dots, a^{x_t}b^{y_t}).
$$
(i) The functions $f(a,b) = a$ and $f(a,b) = b$ are good functions of order $0$.
(ii) If $f(a,b)$ and $g(a,b)$ are good functions of orders $p$ and $q$ respectively, then $\text{gcd}(f(a,b), g(a,b))$ is a good function of order $p+q$, and $f(a,b)g(a,b)$ is a good function of order $p+q+1$.
Prove that if, for some positive integer $n \ge 3$, $f(a,b)$ is a good function of order $k$ with $k \le C_3^n$, then there exist a positive integer $t \le C_2^n$ and $t$ pairs of non-negative integers $(x_1, y_1), \dots, (x_t, y_t)$ such that
$$
f(a,b) = \text{gcd}(a^{x_1}b^{y_1}, \dots, a^{x_t}b^{y_t}).
$$