Let $g:\mathbb{N}\to \mathbb{N}$ be a bijective function and suppose that $f:\mathbb{N}\to \mathbb{N}$ is a function such that: For all naturals $x$, $$\underbrace{f(\cdots (f}_{x^{2023}\;f\text{'s}}(x)))=x. $$ For all naturals $x,y$ such that $x|y$, we have $f(x)|g(y)$. Prove that $f(x)=x$. Proposed by Pulkit Sinha
Problem
Source: India TST 2023 Day 1 P2
Tags: algebra, functional equation, function
14.07.2023 05:51
I present a slightly long but detailed solution! For $x=1$, the first condition give us $f(1)=1$. Furthermore, by the second condition, $x | x\Rightarrow f(x) | g(x)$, for all $x\in\mathbb{N}$. Denote $f^n(x)=\underbrace{f(f(\dots f}_{n\,\,f'\text{s}} (x)\dots))$. Note that, if $f^n(x)=x$, then $f^{kn}(x)=x$, for all $k\in\mathbb{N}$. Thus, $$f(a)=f(b)\Rightarrow f^{(ab)^{2023}}(a)=f^{(ab)^{2023}}(b)\Rightarrow a=b,$$ and we conclude that $f$ is injective. Also, given $y\in \mathbb{N}$, taking $x=f^{y^{2023}-1}(y)$, we get $f(x)=f^{y^{2023}}(y)=y$, and we conclude that $f$ is onto. So, $f$ is a bijective function. Now, choose $y\in\mathbb{N}$ such that $g(y)=1$. If $y>1$, for each $x$ such that $x|y$, we have $f(x)|g(y)=1\therefore f(x)=1$. As $f$ is injective, we get $x=1$, i.e., there's only one $x\in \mathbb{N}$, $x|y$, and this implies that $y=1$. Claim 1: If $p$ is a prime and $g(y)=p$, then $y$ is a prime. In fact, we have $y>1$, because $g(1)=1$. If $x_1, x_2>1$ are distinct natural and $x_1, x_2 | y$, then $f(x_1), f(x_2) | g(y)=p\therefore f(x_1)=f(x_2)=p\therefore x_1 =x_2,$ a contradiction. So, $y$ has a unique divisor greater than 1, i.e. $y$ is a prime. Let $P=\{p_1<p_2<\cdots\}$ be the set of the primes. For each $j\in \mathbb{N}$, let $q_j$ be the prime such that $g(q_j)=p_j$. Then, $f(q_j)|g(q_j)=p_j\therefore f(q_j)=p_j$. Claim 2: If $p, q$ are primes and $f(q)=p$, then $p=q$. Note that $f(q)=p$ implies $f^{m-1}(p)=f^m(q)$. If $p\ne q$, choose $m$ such that $p^{2023} | m-1$ and $q^{2023}|m$. This way we have $f^{m-1}(p)=p$ and $f^m(q)=q$, i.e., $p=q$, a contradiction. That choice is possible, because we can take $m=k\cdot q^{2023}$ and $$m\equiv 1\,(\text{mod}\,p^{2023})\therefore k\cdot q^{2023}\equiv 1\,(\text{mod}\,p^{2023})\therefore k\equiv ( q^{2023})^{-1}\,(\text{mod}\,p^{2023}).$$ So, we conclude that $f(p)=p$, for all $p$ prime. Also, $g(p)=p$, because $g(q_j)=p_j$ implies $f(q_j)=p_j$, and then $q_j=p_j$. Claim 3: If $p$ is a prime, then $f(p^k)=g(p^k)=p^k$, for all $k\in\mathbb{N}$. The proof is by induction. For $k=1$, it's ok. Suppose $g(p^k)=p^k$, for $k=1,2,\dots, n-1$. Take $y\in\mathbb{N}$, $g(y)=p^n$. Then, every prime $q$ such that $q|y$ satisfies $f(q)|g(y)=p^n\therefore q|p^n$. Therefore, $q=p$ and $y=p^{\ell}$. On one hand, $\ell\ge n$, because if $\ell<n$, we get $g(y)=g(p^{\ell})=p^{\ell}<p^n$, and it's a contradiction. By the other hand, if $\ell>n$, for each $x\in\{1,p,p^2,\dots,p^\ell\}$, $f(x)|g(y)=p^{n}$. But, it's not possible, since $p^n$ has exactly $n+1$ divisors and $n+1<\ell+1$. So, $\ell=n$ and $g(p^n)=p^n$. Form this result, we obtain $f(p^k)|g(p^k)=p^k\therefore f(p^k)|p^k$. By induction, suppose that $f(p^k)=p^k$, for $k=0,1,\dots,n-1$. As $f$ is injective and $f(p^n)|p^n$, the only possibility is $f(p^n)=p^n$. Claim 4: $g(y)=y$, for all $y\in\mathbb{N}$. Suppose $y=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot...\cdot p_k^{\alpha_k}$. As $p_j^{\alpha_j}|y$, we have $f(p_j^{\alpha_j})|g(y)\therefore p_j^{\alpha_j}|g(y)$, for all $j=1,\dots, k$. Then, $$y=\prod_{j=1}^{k}p_j^{\alpha_j} | g(y)\therefore y |g(y).$$ We follow with $y\le g(y)$. As $g:\mathbb{N}\rightarrow\mathbb{N}$ is bijective, we must have $g(y)=y$. We can show this easily by induction: suppose that $g(k)=k$, for $k=1,\dots,n-1$. If $g(n)>n$, then for $m>n$, we get $g(m)\ge m>n$ and then $n\notin Range(g)$, a contradiction. So, $g(n)=n$, and the induction is finished. Finally, as $f(x)|g(x)$, we get $f(x)|x$, for all $x\in\mathbb{N}$ and $f(x)\le x$. As $f$ is bijective, we conclude analogously by induction that $f(x)=x$.
23.09.2023 20:26
Claim: $f$ is bijective. Proof: Suppose $f(a) = f(b)$. Then note that $f^{a^{2023}}(a) = a$ and $f^{b^{2023}}(b) = f^{b^{2023}}(a) = b $. Now we see that $(ab)^{2023}$ is a multiple of both $a^{2023}$ and $b^{2023}$, so $f^{(ab)^{2023}}(a)$ equals both $a$ and $b$, which means $a = b$, so $f$ is injective. Surjectivity is obvious. $\square$ Let $d(n)$ denote the divisor function. Claim: $d(y) \le d(g(y))$. Proof: If this were not true, then for any $x\mid y$, there are $d(y)$ possible values for $x$, and less than $d(y)$ possible values for $f(x)$, so $f$ is not injective, contradiction. $\square$ If $g(y) = 1$, then $d(y) \le 1\implies y = 1$, so $g(1) = 1$. If $g(y) = p$ for some prime $p$, then $d(y) \le 2$, so $y = 1$ or $y$ is prime. But we already know that $g(1)$ isn't prime, so $y$ must be prime. Since $x\mid x$, we have $f(x) \mid g(x)$ for all $x$. Now let a cycle of $f$ denote a finite set $\{n,f(n), f(f(n)), \ldots, \}$ for a positive integer $n$. Since $f$ is bijective, $f$ can be partitioned completely into disjoint cycles. For each $x$, the length of the cycle $x$ is in divides $x^{2023}$. Claim: In any cycle other than $\{1\}$, all the elements share a common factor greater than $1$. Proof: Suppose for some cycle $\{a_1, a_2, \ldots, a_k\}$ we had $\gcd(a_1, a_2, \ldots, a_k) = 1$. Notice that the cycle length ($k$) divides all of $a_1^{2023}, a_2^{2023}, \ldots, a_k^{2023}$, so it must be equal to $1$. Then we see that $a_1 = 1$, so the cycle must be $\{1\}$, as desired. $\square$ Claim: $g$ is fixed over primes. Proof: Suppose this was not the case. Then there exists a prime $q\ne p$ with $g(q) = p$. However, since $q$ and $f(q)$ are in the same cycle, they share a common prime factor, which means that $q\mid f(q)\mid g(q) = p$, contradiction. $\square$ Now for any prime $p$, we have for all $x\mid p$ that $f(x) \mid p$, so $f(p)\mid p$. We already know that $p\mid f(p)$, so $f(p) = p$ for all primes $p$. Claim: $g(p^n) = p^n$ for all positive integers $n$ and primes $p$. Proof: We induct on $n$. Suppose $g(p^k) = p^k\forall k <n$ and primes $p$. Notice that $x\mid p^k\implies f(x)\mid p^k$. Since $f$ is injective, \[\{1, p, p^2, \ldots, p^k\} = \{f(1), f(p), f(p^2), \ldots, f(p^k)\}\]for all $k < n$. Notice that \[ \{1, p, \ldots, p^k\} = \{1, p, \ldots, p^{k-1}, p^k\} = \{f(1), f(p), \ldots, f(p^{k-1}), p^k\}\]For this to be equal to $\{f(1), f(p), \ldots, f(p^{k-1}), f(p^k)\}$, we must have $p^k = f(p^k)\forall 0\le k < n$. Now, we have $p^k\mid y \implies p^k \mid g(y)$ for $k < n$. Setting $k = n - 1$ and $y = p^n$ gives that $p^{n-1} \mid g(p^n)$. Now suppose we had $g(a) = p^n$ for some $a$. Then $x\mid a\implies f(x) \mid p^n$. But if $f(x) \in \{1, p, p^2, \ldots, p^{n-1}\}$, then $x$ is a power of $p$, which means that there can be at most one divisor of $a$ that isn't a power of $p$. This is clearly impossible unless $a$ is a power of $p$ or a prime unequal to $p$. If $a$ is a prime not equal to $p$, then $f(a) = a$, which doesn't divide $p^n$, so $a$ must be a power of $p$. Since $d(a) \le d(g(a)) = n + 1$, we have $a \le p^n$. If $ a< p^n$, then $g(a) = a\ne p^n$, so $a = p^n$, which implies $g(p^n) = p^n$. $\square$ Claim: $f(p^n) = p^n$ for all primes $p$ and positive integers $n$. Proof: Induct on $n$. If it was true for all $k < n$, then note that $x\mid p^n \implies f(x) \mid g(p^n) = p^n$. Thus, $f(p^n) \mid p^n$. If $f(p^n) = p^b$ for some $b < n$, then $f(p^n) = f(p^b)$, contradiction to injectivity. Therefore, $f(p^n) = p^n$. $\square$ Note $p^k\mid y \implies p^k\mid g(y)$. Therefore, all positive integers $x$ satisfy $x\mid g(x)$. Claim: $\nu_p(x) = \nu_p(g(x)) $ for all primes $p$ and positive integers $x$. Proof: Suppose not for some $x$ ($\nu_p(x) < \nu_p(g(x))$). Since $g$ is bijective, the orbit $\{x, g(x), g(g(x)), \ldots, \}$ cycles. Consider the $\nu_p$ of this orbit. Since $\nu_p(x) < \nu_p(g(x))$, the $\nu_p$ of this orbit increases at some point, but since it cycles, it must decrease at some point also. Thus, there exists $c$ in the cycle such that $\nu_p(c) > \nu_p(g(c))$, which is absurd since $c \mid g(c)$. $\square$ Therefore $g(x) = x$ for all $x$. Now for all $x\mid y$, $f(x) \mid y$. This implies that $f(y) \mid y$, so $f$ is nonincreasing. Since $\{y, f(y),f(f(y)), \ldots, \}$ repeats at some point, $f(y) = y$ for all $y\in \mathbb{N}$.
08.10.2023 18:42
The functional graph of $f$ is obviously the union of disjoint cycles, and since $g$ is a bijection its functional graph is the union of disjoint cycles and "chains" which extend infinitely in both directions. Claim: Actually, no chains exist. Proof: Suppose otherwise and consider an arbitrary chain with minimal element $m$. There must exist arbitrarily large elements of this chain which occur before $m$. Pick some $e$ large enough to not appear in the $f$-cycles of $1,\ldots,m$ and then iterate the second condition, starting from $(x,y)=(e,e)$, to get $f^k(e) \mid m$ for some $k$. But we also have $f^k(e)>m$: contradiction. $\blacksquare$ Note that since $f$ is injective, the second condition implies that $g(y)$ has at least as many divisors as $y$, and since $g$ is the union of disjoint cycles in fact $g(y)$ and $y$ must have the same number of divisors. Fix a prime $p$. I claim that all the elements of the $f$-cycle containing $p$ are divisible by $p$. Indeed, if this cycle has length $1$ its obvious, otherwise it has length $p^k$ for some $1 \leq k \leq 2023$. But this cycle length must also divide $e^{2023}$ for every element $e$ in the cycle, hence proven. This means that $p \mid y \implies p \mid f(p) \mid g(y)$. Iterating this and considering every $p$ implies that all the elements of any fixed $g$-cycle have the same set of prime divisors. This result, as well as $y$ and $g(y)$ having the same number of divisors, immediately implies that every prime power gets sent to itself by $g$. Then every prime power also gets sent to itself by $f$, since if $p^k$ is the smallest prime power not sent to itself we have $f(p^k) \mid p^k$, evidently contradicting minimality. This implies that for any prime $p$, the $p$-adic valuations of every element of a $g$-cycle are the same, since we have $p^k \mid y \implies p^k \mid g(y)$. Thus every $g$-cycle has length $1$, i.e. $g$ is the identity. Finally, this means $x \mid y \implies f(x) \mid y$. Thus consider $x=y=e$ where $e$ is the minimal element of some $f$-cycle. Then $f(e) \mid e$ as well, hence the cycle is length $1$. Thus $f$ is the identity as well. $\blacksquare$
08.04.2024 09:36
This is a typical "Arrows" problem. We show that for every integer $x$, we have $f(x)=g(x)=x$. Claim: $f$ is bijective. Proof. The first equation gives us at least one solution to $f(x)=t$ by setting $x=f^{t^{2023}-1}(t)$. So, the function is surjective. We now show that it is injective. Note that for any $n$, we have $f^{x^{2023}n}(x)=x$. Injectivity at $1$, is trivial, the first equation gives $f(1)=1$ so if $f(x)=1$ for $x>1$ then $x=f^{x^{2023}}(x)=f^{x^{2023}-1}(f(x))=f^{x^{2023}-1}(1)=1$, which contradicts $x=1$. So, if $x,y \in \mathbb N_{>1}$ exist such that $f(x)=f(y)$, then $x=f^{x^{2023}y^{2023}}(x)=f^{x^{2023}y^{2023}}(y)=y$. So, the function is injective and surjective, and hence bijective. $\blacksquare$ Note that if $g(1)\ne1$, then there exists $q$ such that $g(q)=1$ but we know $f(q)\mid g(q)=1$ which forces $f(q)=1$ and hence $q=1$ by injectivity. Consider the infinite directed graph $G$ such that every vertex represents a unique positive integer, and edge $u\longrightarrow v$ exists if and only if $v=f(u)$. Since $f$ is bijective, so by the first condition we have that $G$ is composed entirely of disjoint directed cycles and/or fixed points. Consider a cycle $u_1, u_2, \ldots, u_m$. The first condition gives that $m\mid u_i^{2023}$ for each $1\leq i\leq m$. In particular, if there exists a prime number $p$ in this cycle, then $m$ is a power of that prime, and hence all terms of the cycle are divisible by $p$. Claim: For every prime $p$, we have $f(p)=g(p)=p$. Proof. Since $g$ is bijective, there exists unique $x$ for which $g(x)=p$. So, if $d$ is a divisor of $x$, it means $f(d)\mid p\Longrightarrow f(d)\in\{1,p\}$. So, $x$ has at most two divisors which means $x$ is prime and $f(x)=g(x)=p$. [The other case, $x=1$, is trivially not possible as then $p\mid g(x)$ for every $x$ which contradicts surjectivity of $g$.] However, if $f(x)\ne x$, then $f(x)=p$ lies in the cycle of $x$ and hence $p\mid x$, which forces $x=p$. So, $f(p)=p=g(p)$, as claimed. $\blacksquare$ Claim: $g(n)=f(n)=n$ for all positive integers $n$. Proof. We perform strong induction on the number of divisors of $n$. The base case for $n$ being prime has been done in the above claim. Suppose that $n$ is composite and has $k$ distinct factors, and if any number $n_1$ has at most $k-1$ distinct factors then $f(n_1)=g(n_1)=n_1$. Let $1=d_1, d_2, \ldots, d_k=n$ be the $k$ factors of $n$ with $d_i<d_j$ for $1\leq i<j\leq k$. Let $n'$ be the number for which $g(n')=n$. By induction hypothesis, $n'$ must have at least $k$ distinct factors. Suppose $n_1$ has $k'$ factors which are $1=e_1, e_2, \ldots e_{k'}=n'$ with $e_i<e_j$ for $1\leq i<j\leq k'$. Then, from the second property, we have that $\{f(e_1), f(e_2), \ldots, f(e_{k'})\}\subseteq\{d_1, d_2, \ldots, d_k\}$. This forces $k'=k$ as each $f(e_i)$ is distinct. Note that for any divisor $e_i$ with $i<k$, it has at most $k-1$ factors, and hence our induction hypothesis gives $g(e_i)=f(e_i)=e_i$ for each $1\leq i<k$. So, we have $\{e_1<e_2<\cdots<e_{k-1}<n'\}=\{d_1<d_2<\cdots<d_{k-1}<n\}$. This forces $e_i=d_i$ for each $1\leq i<k$, and hence $n=n'$. So, $f(n)=g(n)=n$, and the induction is complete. $\blacksquare$