MathDB

Denote the set of all positive integers by

\mathbb{N}

, and the set of all ordered positive integers by

\mathbb{N}^2

. For all non-negative integers

k

, define good functions of order k recursively for all non-negative integers

k

, among all functions from

\mathbb{N}^2

\mathbb{N}

as follows:
(i) The functions

f(a,b)=a

and

f(a,b)=b

are both good functions of order

0

.
(ii) If

f(a,b)

and

g(a,b)

are good functions of orders

p

and

q

, respectively, then

\gcd(f(a,b),g(a,b))

is a good function of order

p+q

, while

f(a,b)g(a,b)

is a good function of order

p+q+1

.
Prove that, if

f(a,b)

is a good function of order

k\leq \binom{n}{3}

for some positive integer

n\geq 3

, then there exist a positive integer

t\leq \binom{n}{2}

and

t

pairs of non-negative integers

(x_1,y_1),\ldots,(x_n,y_n)

such that

f(a,b)=\gcd(a^{x_1}b^{y_1},\ldots,a^{x_t}b^{y_t})

holds for all positive integers

a

and

b

.
Proposed by usjl

N