Functional divisibility

For discussing Olympiad Level Number Theory problems
User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm

Functional divisibility

Unread post by Phlembac Adib Hasan » Mon Nov 07, 2016 10:12 pm

$ k$ is a given natural number. Find all functions $ f: \mathbb{N}\rightarrow\mathbb{N}$ such that for each $ m,n\in\mathbb{N}$ the following holds: \[ f(m)+f(n)\mid (m+n)^k\]
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: Functional divisibility

Unread post by rah4927 » Thu Nov 10, 2016 12:59 pm

Let $P(m,n)$ be the statement $f(m)+f(n) | (m+n)^k$ .

We prove that the only solution is $f(n)=n$. Note that this indeed works.

Claim 0: For two polynomials $P$ and $Q$ such that $P \nmid Q$, there are only finitely many integers $n$ such that $P(n)|Q(n)$ .

Proof: Apply division algorithom on $P$ and $Q$ . Suppose $$Q(x)=P(x)T(x)+R(x)$$ where the degree of $R(x)$ is smaller than that of $P(x)$ . Note that $R(x) \neq 0$ since $P \nmid Q$ . So $P(n)$ must divide $R(n)$, but this is possible only for a finite number of integers since very soon enough, $P(x)$ will be much greater than $R(x)$ is absolute value, since $P$ has a larger degree. Therefore our claim is proved.

Claim 1: There are infinitely many numbers $n$ such that $f(n)=n$


$$P(1, 1) : f(1) | 2^{k-1} \Rightarrow f(1) = 2^i$$

Let $p$ be a prime.

$$P(1,p-1) : f(1)+f(p-1)|p^k$$
$$2^i+f(p-1) = p^j$$
$$f(p-1) = p^j-2^i$$

We use this with a combination of claim-$0$ to prove that $f(p-1)=p-1$ for sufficiently large $p$.

$$P(p-1,p-1): f(p-1)|2^{k-1}(p-1)^k$$
$$p^j-2^i | 2^{k-1}(p-1)^k $$

Now recall that $i,j$ are both bounded from above by $n$. Hence, there are only a finite number of $(i,j)$ pairs. For every such pair, we get one divisibility condition. For example, inputting $(i,j)=(2,3)$, we get the the divisibility $p^3-2^2 | 2^{k-1}(p-1)^k$ . But this has only a finite number of solutions by claim $0$. Similarly, for EVERY such pair, there are only a finite number of solutions of the above divisibility, except when $(i,j)=(0,1)$, in which case the divisibility becomes $p-1|2^{k-1}(p-1)^k$ which is always true. Since the divisibility must be true for all primes, we can say that for large enough primes, $(i,j)=(0,1)$ which basically implies that $f(p-1)=p^j-2^i=p-1$ and we are done.

Claim 3: $f(n)=n$ for all $n$.

Proof: Fix $m$. Let $n$ be a fixed point.

$$P(m,n) : f(m) + n |(m+n)^k \Rightarrow f(m)+n | (m-f(m))^k$$

The right side is constant but the left side can be increased arbitrarily by increasing $n$. This is only possible when the right side is $0$ i.e. when $f(m)=m$.

Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: Functional divisibility

Unread post by tanmoy » Sat Nov 12, 2016 2:27 pm

Let $P(x,y)$ be the assertion $f(x)+f(y) \mid (x+y)^{k}$.

(1) $f(1)=1$
Proof:First assume that $f(1) \neq 1$.$P(1,1)$ implies $f(1)=2^{a}$ for some non-negative integer $a$.

$P(2,2)$ implies $f(2)=2^{b}$ for some non-negative integer $b$.

$P(1,2)$ implies that $f(1)+f(2) \mid 3^{k}$.If both $f(a),f(b)$ are even,then we get a contradiction as an even integer doesn't divide an odd integer.So,one of them is odd i.e. equals to $1$.As we assumed that $f(1) \neq 1$,so,$f(2)=1$.

So,$2^{a}+1=3^{r}$........(i),then by Zsigmondy's Theorem,$a=1$ or $3$.

Now,$P(1,3)$ implies that $f(1)+f(3) \mid 4^{k}$.So,$f(1)+f(3)=2^{i}$ where $i$ is a positive integer.Since $f(1)$ is a power of $2$,so,$f(1)=f(3)$.

Now,$P(2,3)$ implies that $1+2^{a} \mid 5^{k}$ $\Rightarrow$ $2^{a}+1=5^{r}$.......(ii).From (i),we know that $a=1$ or $3$,but none is valid for (ii),a contradiction.So our first assumption was wrong and $f(1)=1$.

(2) $f(p-1)=p-1$
Proof:$P(1,p-1)$ implies that $f(p-1)=p^{s}-1$.

$P(p-1,p-1)$ implies that $f(p-1)=p^{s}-1 \mid 2^{k-1}(p-1)^{k}$.So ,the set of distinct prime divisors of $p-1$ and $p^{s}-1$ is same.But from Zsigmondy's Theorem,we know that this can be possible if and only if $s=1$ i.e. $f(p-1)=p-1$.

(3) $f(n)=n$ for all $n \in \mathbb{N}$
Proof:$P(n,p-1)$ implies that $f(n)+p-1 \mid (n+p-1)^{k}$.
Now,$f(n) \equiv -(p-1)$ $\text{(mod}$ $f(n)+p-1)$.
$\Rightarrow$ $n-f(n) \equiv n+p-1$ $\text{(mod}$ $f(n)+p-1)$.
$\Rightarrow$ $(n-f(n))^{k} \equiv (n+p-1)^{k} \equiv 0$ $\text{(mod}$ $f(n)+p-1)$

Here the value of $(n-f(n))^{k}$ is fixed for each particular $n$.But if $p \to \infty $, $(f(n)+p-1) \to \infty$.Therefore,$(n-f(n))^{k}=0$ and $f(n)=n$ for all $n \in \mathbb{N}$.
"Questions we can't answer are far better than answers we can't question"

Post Reply