Câu hỏi 89
Ký hiệu $\mathbb{N}$ là tập hợp các số nguyên dương và $\mathbb{N}^2$ là tập hợp các cặp số nguyên dương. Trong các hàm số từ $\mathbb{N}^2$ vào $\mathbb{N}$, với mỗi số nguyên không âm $k$, ta định nghĩa đệ quy các hàm tốt cấp $k$ như sau:
(i) Các hàm $f(a,b) = a$ và $f(a,b) = b$ là các hàm tốt cấp $0$.
(ii) Nếu $f(a,b)$, $g(a,b)$ lần lượt là các hàm tốt cấp $p$ và cấp $q$ thì $\text{gcd}(f(a,b), g(a,b))$ là hàm tốt cấp $p+q$, và $f(a,b)g(a,b)$ là hàm tốt cấp $p+q+1$.
Chứng minh rằng nếu với một số nguyên dương $n \ge 3$ nào đó, $f(a,b)$ là một hàm tốt cấp $k$ với $k \le C_3^n$, thì tồn tại số nguyên dương $t \le C_2^n$ và $t$ cặp số nguyên không âm $(x_1, y_1), \dots, (x_t, y_t)$ sao cho
$$
f(a,b) = \text{gcd}(a^{x_1}b^{y_1}, \dots, a^{x_t}b^{y_t}).
$$
(i) Các hàm $f(a,b) = a$ và $f(a,b) = b$ là các hàm tốt cấp $0$.
(ii) Nếu $f(a,b)$, $g(a,b)$ lần lượt là các hàm tốt cấp $p$ và cấp $q$ thì $\text{gcd}(f(a,b), g(a,b))$ là hàm tốt cấp $p+q$, và $f(a,b)g(a,b)$ là hàm tốt cấp $p+q+1$.
Chứng minh rằng nếu với một số nguyên dương $n \ge 3$ nào đó, $f(a,b)$ là một hàm tốt cấp $k$ với $k \le C_3^n$, thì tồn tại số nguyên dương $t \le C_2^n$ và $t$ cặp số nguyên không âm $(x_1, y_1), \dots, (x_t, y_t)$ sao cho
$$
f(a,b) = \text{gcd}(a^{x_1}b^{y_1}, \dots, a^{x_t}b^{y_t}).
$$