Finding all functions $ f : \mathbb N^*\to\mathbb N^*$ such that for every $ x , y \in \mathbb N ^ * $, $ f ( x ) + f ( y ) \mid x ^ n + y ^ n $

Question

Let $\mathbb N^*$ be the set of positive integers and $n$ be a fixed positive integer. How many functions $ f : \mathbb N^*\to\mathbb N^*$ are there such that for all positive integers $x$ and $y$, $f(x) + f(y)$ divides $x^n + y^n$?

Answer 1

Let $n=2^ks$ with $s$ being odd. I will prove that every solution $f:\Bbb N_1 \to \Bbb N_1$ is of the form $f(x)=x^{2^kt}$ where $t\mid s$ is fixed.

First, with $x,y=1$, we get $$2f(1)=f(1)+f(1)\mid 1^n+1^n=2,$$ so $f(1)=1$. Now, for a prime $p$, we have $$2f(p)=f(p)+f(p)\mid p^n+p^n=2p^n.$$ That is, $f(p)=p^{d_p}$ for some integer $d_p$, $0\leq d_p\leq n$, possibly depending on $p$. Now, $$p^{d_p}+1 =f(p)+f(1)\mid p^n+1.$$ It follows that $d_p=2^k t_p$ for some integer $t_p \mid s$, noting that $$\gcd(a^b+1,a^c+1)=\gcd(a+1,2)\in\{1,2\}$$ if $v_2(b)\neq v_2(c)$, and $$\gcd(a^b+1,a^c+1)=a^{\gcd(b,c)}+1$$ if $v_2(b)=v_2(c)$.

Since there are infinitely many primes, there exists $t\mid s$ such that $t=t_p$ for infinitely many primes $p$. We can prove that $t_q=t$ for every prime $q$, but this is not important. You can omit this step.

This is an unnecessary step. We claim that $t_q=t$ for all primes $q$. Let $p$ and $q$ be arbitrary primes, with the condition that $t_p=t$. We have $$p^{2^kt_p}+q^{2^kt_q}=f(p)+f(q)\mid p^n+q^n=\big(p^{2^kt_p}\big)^{\frac{s}{t_p}}+q^n.$$ Because $p^{2^kt_p}\equiv -q^{2^kt_q}\ \left(\text{mod}\ p^{2^kt_p}+q^{2^kt_q}\right)$, we must have $$p^{2^kt_p}+q^{2^kt_q}\mid \big(-q^{2^kt_q}\big)^{\frac{s}{t_p}}+q^n=-q^n\left(q^{n\left(\frac{t_q}{t_p}-1\right)}-1\right).$$ So, $$p^{2^kt}+q^{2^kt_q}\mid q^n\left(q^{n\left(\frac{t_q}{t}-1\right)}-1\right)$$ for all primes $p$ such that $t_p=t$. Since there are infinitely many such $p$, we must have $$q^{n\left(\frac{t_q}{t}-1\right)}-1=0$$ or $t_q=t$, for every prime $q$.

Now, for any $x\in\Bbb{N}_1$, we have $$f(x)+p^{2^kt}=f(x)+f(p)\mid x^n+p^n=x^n+\left(p^{2^kt}\right)^{\frac{s}{t}}$$ for any prime $p$ (if you skip the step in the hidden box, you can take $p$ to be any prime such that $t_p=t$). As $p^{2^kt}\equiv -f(x)\ \left(\text{mod}\ f(x)+p^{2^kt}\right)$, we conclude that $$f(x)+p^{2^kt}\mid x^n+\big(-f(x)\big)^{\frac{s}{t}}=x^n-\big(f(x)\big)^{\frac{s}{t}}$$ for all primes $p$ (if you skip the step in the hidden box, you can take $p$ to be any prime such that $t_p=t$). This shows that $$x^{2^ks}=x^n=\big(f(x)\big)^{\frac{s}{t}}$$ for every positive integer $x$, and so $$f(x)=x^{2^kt},$$ as claimed.