MathDB

Functional equation with gcd

Source: 2021 Thailand Online MO P8 (Mock TMO contest)

April 6, 2021

functional equationnumber theorygreatest common divisor

Problem Statement

Let

\mathbb N

be the set of positive integers. Determine all functions

f:\mathbb N\times\mathbb N\to\mathbb N

that satisfy both of the following conditions:
[*]

f(\gcd (a,b),c) = \gcd (a,f(c,b))

for all

a,b,c \in \mathbb{N}

. [*]

f(a,a) \geq a

for all

a \in \mathbb{N}