This problem was proposed by me.

Nice Problem BTW

Fun problem! Taiwan TST 2022 wrote: Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f\colon \mathbb{N}\to \mathbb{N}$ such that $mf(m)+(f(f(m))+n)^2$ divides $4m^4+n^2f(f(n))^2$ for all positive integers $m$ and $n$.

You can't claim F to be a polynomial

math_comb01 wrote: Fun problem! Taiwan TST 2024 wrote: Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f\colon \mathbb{N}\to \mathbb{N}$ such that $mf(m)+(f(f(m))+n)^2$ divides $4m^4+n^2f(f(n))^2$ for all positive integers $m$ and $n$.

my bad

bookstuffthanks wrote: You can't claim F to be a polynomial I never claimed $f$ a polynomial, I fixed $m$ and view $(n+f(f(m)))^2+mf(m)$ as polynomial in $n$ ismayilzadei1387 wrote: I think it is not correct Elaborate?

i would like to give steps that i solve with. $f(1)=1$ $ff(2)=f(2)=2$ Let $p$ be an arbitrary prime different from $2$. $P(1,p)$ and $P(p,1)$ yield. $(2+2p+p^2) \vert (ff(p)^2+2p+2)$ 1.$\gcd(ff(p),p)=p$ then $ff(p)=pk$ and $k \geq p+2$ or $k=1$ so $ff(p) \geq p^2+2p$ or $ff(p)=p$ if $ff(p) \geq p^2+2p$ it is obvious contradiction. thus,$ff(p)=p$ which gives us $f(p)=p$ for all prime $p$ with motivation $P(p,n)$ gives us $(2p^2+2pn+n^2) \vert (4p^4+n^4)$ and $( 2p^2+2pn+n^2) \vert (4p^4+n^2ff(n)^2)$ thus $(2p^2+2pn+n^2) \vert (n^2(n^2-ff(n)^2))$ thus $n^2=ff(n)^2$ if we choose $p$ sufficiently large $ff(n)=n$ from there it is easy to get $f(n)=n$ Now there is a other case $\gcd(ff(p),p)=1$ then form $P(2,p)$ $P(p,2)$ and some inequalities there exists some $p$ such that the divisblity doesn't exist.

ismayilzadei1387 wrote:

$f \equiv id$ is clearly a solution by sophie germain identity.

math_comb01 wrote: ismayilzadei1387 wrote:

$f \equiv id$ is clearly a solution by sophie germain identity. ohh you are right there is missing that $\gcd(f(p),p)=p$ and i give contradiction for $\gcd(f(p),p)=1$ thanks

Here is a complete solution. Solved with Adhitya and Rushil. We will use the lemma that if a $3 \pmod 4$ prime $p \mid a^2+b^2$, then $p \mid a,b$ in the following solution, at multiple places without mention. Claim 1 : $mf(m)$ is a perfect square. Proof : We first prove the following lemma : Lemma : If $a$ is not perfect square, then there exist infinitely many primes $p$ such that $p \equiv 3 \pmod 4$ and $p \mid n^2+a$ for some $n \in \mathbb{N}$. Proof : Let $a= \prod{p_i}^{\alpha_i}$ and since $a$ is not a perfect square, wlog let $\alpha_1$ be odd. For now assume $p_i \neq 2$. For prime $p \equiv 3 \pmod 4$, observe that $$\left(\frac{a}{p}\right) = \prod \left(\frac{p_i}{p}\right)^{\alpha_i} = \prod \left(\left(\frac{p}{p_i}\right)\left(\frac{-1}{p_i}\right)\right)^{\alpha_i}$$By CRT and Dirichlet, consider the primes satisfying the following 3 conditions to finish. $p \equiv -1 \pmod {p_i}$ for all $i>1$. $p \equiv \text{NQR} \pmod {p_1}$. $p \equiv 3 \pmod 4$. If $p_1=2$, then setting $p \equiv 3\pmod 8$ so that $\left(\frac{2}{p}\right) = -1$ in place of 2nd condition works. $\blacksquare$ Now back to the claim. Suppose $mf(m)$ is not perfect square. By the lemma, take prime $p>2m^2$, such that $p \equiv 3 \pmod 4$ and $p \mid (n+f(f(m)))^2+mf(m)$ for some $n \in \mathbb{N}$. By $P(m,n) : p \mid 4m^4+n^2f(f(n))^2 \implies p \mid 2m^2,nf(f(n))$. Since $p>2m^2$, we have a contradiction. Claim 2 : $f(m)=m$, if $m$ is product of pairwise distinct $3 \pmod 4$ primes. Proof : Since $mf(m)$ and $f(m)f(f(m))$ are perfect squares, it forces $mf(f(m))$ to be a perfect square as well. Suppose $m$ is product of pairwise distinct $3 \pmod 4$ primes. Hence let $f(m)=mx^2$ and $f(f(m))=my^2$ for some $x,y \in \mathbb{N}$. $$P(m,m) : x^2 + (y^2+1)^2 \mid m^2(4+y^4)$$We will show that $\gcd(m,x^2+(y^2+1)^2)=1$. Suppose not. Then some $3 \pmod 4$ prime $p \mid x^2+(y^2+1)^2 \implies p \mid x, y^2+1$. In particular $p \mid y^2+1$ is a contradiction. Hence $x^2+(y^2+1)^2 \mid 4+y^4$ which implies $x=y=1$ by bounding. Hence $f(m)=m$ and the claim is proven. $\blacksquare$ Claim 3 : $f(f(n))=n$ for all $n$. Proof : Let $m$ be such that it is product of pairwise distinct $3 \pmod 4$ primes. Note that by Sophie Germain Identity $m^2+(m+n)^2 \mid 4m^4 + n^4$. $$P(m,n) : m^2+(m+n)^2 \mid 4m^4 + n^2f(f(n))^2 \implies m^2+(m+n)^2 \mid n^4 - n^2f(f(n))^2$$On taking large enough $m$, we infer that $f(f(n))=n$ and the claim is proven. $\blacksquare$ Claim 4 : $f(m)=m$ for all $m$. Proof : Let $k$ be a sufficiently large integer. $P(m,k-m) : mf(m) + k^2 \mid 4m^4 +(k-m)^4 \dots (1)$ and $P(f(m),k-f(m)) : mf(m) + k^2 \mid 4f(m)^4 +(k-f(m))^4 \dots(2)$. Subtracting the two terms on the RHS from (1) and (2) and replacing $k^2$ with $-mf(m)$ we infer that $$mf(m) + k^2 \mid 4k\big(f(m)^3-m^3 - mf(m)(f(m)-m)\big) + 5(f(m)^4-m^4)-6mf(m)(f(m)^2-m^2) \implies f(m)^3-m^3 - mf(m)(f(m)-m) =0$$The last step follows since LHS is $\mathcal{O}(k^2)$ and RHS is $\mathcal{O}(k)$. Now it follows that $f(m)=m$ and the claim is proven. $\blacksquare$ Hence we are done

The only solution is $\boxed{f(m) = m}$ for all positive integers $m$, which works. Now we prove it's the only solution. Let $P(m,n)$ be the assertion that\[ mf(m) + (f(f(m)) + n)^2 \mid 4m^4 + n^2 f(f(n))^2 = (2m^2)^2 + (nf(f(n)))^2 \]$P(1,1): f(1) + (f(f(1)) + 1)^2 \mid f(f(1))^2 + 4$. By size, this implies that $2f(f(1)) + f(1) + 1 \le 4$, so $f(1) = 1$. $P(1,n): (n+1)^2 + 1 \mid n^2 f(f(n))^2 + 4$. Claim: For each positive integer $m$, $mf(m) $ is a quadratic residue modulo all $3\pmod 4$ primes. Proof: Suppose otherwise for some $m$, $mf(m)$ wasn't a quadratic residue modulo $p$, where $p$ is a $3\pmod 4$ prime. This implies that we can choose $n$ satisfying $p\mid mf(m) + (f(f(m)) + n)^2$, now Fermat's Christmas Theorem implies that $p$ divides $2m^2$, but then $mf(m)\equiv 0\pmod p$ is a quadratic residue modulo $p$, absurd. $\square$ Claim: $mf(m)$ is a perfect square for all positive integers $m$. Proof: Suppose otherwise for some $m$. Let $c = mf(m)$ and $q$ be a prime factor with $\nu_q(c)$ is odd. We now construct a prime $P$. For each prime divisor $r\mid c$ with $r\ne q$, let $P \equiv -1\pmod r$. Additionally, let $P\equiv 1\pmod q$ if $q\equiv 3\pmod 4$ and $P$ be any quadratic nonresidue mod $q$ if $q\equiv 1\pmod 4$. This is possible by CRT. This construction implies $\left( \frac rP \right) = 1$ for all primes $r\mid c$ and $r\ne q$ and $\left( \frac qP \right) = -1$. Hence $\left( \frac cP \right) = -1$, implying that $c$ isn't a quadratic residue modulo $P$, contradiction since $P$ is a $3\pmod 4$ prime. $\square$ $P(m,1): mf(m) + (f(f(m)) + 1)^2 \mid 4m^4 + 1$. $P(1,n): (n+1)^2 + 1 \mid (nf(f(n))) ^2 + 4$. From $P(1,n)$ combined with the fact that $(n+1)^2 + 1 \mid n^4 + 4$ (which holds by Sophie Germaine), we find that $(nf(f(n)))^2 \equiv n^4 \pmod{n^2 + 2n + 2}$, implying that $f(f(n))^2 \equiv n^2 \pmod{n^2 + 2n + 2}$ for odd $n$. Notice that $f(n) f(f(n))$ is a square, implying that $n f(f(n)) $ is also a square. Claim: $f(f(p)) = p$ for all odd primes $p$. Proof: Suppose otherwise for some prime $p$. Notice that $p$ must divide $f(f(p))$, so let $f(f(p)) = kp$. Hence $(kp)^2 \equiv p^2 \pmod{p^2 +2p + 2}$, but since $p$ and $p^2 + 2p + 2$ are relatively prime and $k > 1$, $k^2 > p^2 + 2p + 2\implies k > p + 1$. Now notice that $P(p,1)$ implies that $pf(p) + (kp + 1)^2 \mid 4p^4 + 1$. Since this exceeds $p^4$ (because $kp > p(p+1) > p^2$ ), we must have $pf(p) + (kp + 1)^2 = 4p^4 + 1$ (as $2, 3, 4$ do not divide $4p^4 + 1$). Now notice that $p$ divides $f(p)$, so taking the equation modulo $p^2$, we see that $2kp \equiv 0\pmod p^2$, so $p$ divides $k$. However, this means that $p^2$ divides $k$ (as $kp$ is a square), so the LHS is clearly larger than the RHS. $\square$ Claim: $f(p) = p$ for all sufficiently large odd primes $p\equiv 3\pmod 4$. Proof: Suppose otherwise for some prime $p$. $P(p,p): pf(p) + 4p^2 \mid 5p^4$, which means that $f(p) + 4p \mid 5p^3$. Since $4p + f(p) \ge 5p$ as $p\mid f(p)$, we must have that $f(p) \in \{p, p^2 - 4p, p^3 - 4p, 5p^2 - 4p, 5p^3 - 4p\}$. $P(p,1): pf(p) + (p+1)^2 \mid 4p^4 + 1$. If $f(p) \ge p^3 - 4p$, notice we can choose $p$ large enough such that $p(p^3 - 4p) > \frac{4p^4 + 1}{5}$. Notice that $2,3,4$ do not divide $4p^4 + 1$. Hence $pf(p) + (p+1)^2 = 4p^4 + 1$. Again, taking modulo $p^2$ gives that $2p \equiv 0\pmod p^2$, absurd. Hence $f(p) \in \{p, p^2 - 4p, 5p^2 - 4p\}$. Since $pf(p)$ is a square, it must leave the same remainder as $p$ when divided by $4$. However, $p^2 - 4p$ and $5p^2 - 4p$ are different from $p$ modulo $4$ as they are $1\pmod 4$. Hence $f(p) = p$. $\square$ Let $p$ be a sufficiently large prime that is $3\pmod 4$. $P(p,n): p^2 + (n+p)^2 \mid 4p^4 + n^2 f(f(n))^2$. However, the LHS of this also divides $4p^4 + n^4$ by Sophie Germain. Hence\[ p^2 + (n+p)^2 \mid n^2 f(f(n))^2 - n^4 = n^2 (f(f(n)) - n) (f(f(n)) + n)\]Taking $p$ large gives $f(f(n)) = n$ for all positive integers $n$. Hence the equation becomes\[mf(m) + (m+n)^2 \mid n^4 + 4m^4 = (n^2 + 2m^2 - 2mn)(n^2 + 2m^2 + 2mn)\] Hence\[mf(m) + (m+n)^2 \mid n^4 + 4m^4 - (n^2 + 2m^2 - 2mn) (mf(m) + (m+n)^2) = m(n^2 + 2m^2 - 2mn)(f(m) - m)\]But then $mf(m) + (m+n)^2$ must also divide $m (m^2 - 4mn + mf(m)) (f(m) - m)$. Choose $n$ such that $\gcd(m,n) = 1$. Then $mf(m) + (m+n)^2$ must divide $(m - 4n + f(m))(f(m) - m)$. If $f(m) \ne m$, then choosing $n$ sufficiently large gives a size contradiction (since the degree of the LHS is greater than that of the RHS). Hence $f(m) = m$ for all positive integers $m$.