Family Of Functions

For discussing Olympiad Level Number Theory problems
User avatar
zadid xcalibured
Posts:217
Joined:Thu Oct 27, 2011 11:04 am
Location:mymensingh
Family Of Functions

Unread post by zadid xcalibured » Tue Apr 16, 2013 4:28 am

Let $n \geq 1$ be an odd integer.Determine all functions $f$ from the set of integers to itself such that for all distinct integers $x$ and $y$,$f(x)-f(y)|x^{n}-y^{n}$.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Family Of Functions

Unread post by *Mahi* » Wed Apr 17, 2013 11:01 am

Too much similarity with 2004 N3 in one problem.

Let the assertion $P(x,y) \Longrightarrow f(x)-f(y) \mid x^n - y^n$
If $f(x)$ is a solution to the given equation, then so is $f(x)+c$, so WLOG let $f(0)=0$.
So, we have $f(x) \mid x^n \; \forall x \in \mathbb Z$

And thus, $f(1) \mid 1 \Rightarrow f(1) = 1$ or $-1$.
Now, if $f$ is a solution, then so is $-f$, so WLOG let $f(1) = 1$

Now, for any $p$, $f(p) \mid p^n \Rightarrow f(p) = p^k, k \le n$
$P(p,1) \Rightarrow p^k - 1 \mid p^n -1 \Rightarrow k \mid n$.

Now, as $n$ has finitely many divisors, there exists a $k \mid n$ such that $f(p) = p^k$ for infinitely many primes $p$.

Again $P(x,p) \Rightarrow f(x) - f(p) = f(x) - p^k \mid x^n - p^n$ along with $f(x) - p^k$ $ \mid f(x)^{n/k} - (p^k)^{n/k}$ implies that $f(x) - p^k \mid x^n - f(x)^{n/k}$.

Now we have $f(x) - p^k \mid x^n - f(x)^{n/k}$ for infinitely many primes $p$, so $x^n -f(x)^{n/k} = 0$, or $f(x)^{n/k} = x^n \Rightarrow f(x) = x^k \; \forall x\in \mathbb Z$

So the solutions are, $f(x) = ax^d+b$, where $a=1 \text{ or } -1, d \mid n$
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: Family Of Functions

Unread post by Tahmid Hasan » Wed Apr 17, 2013 11:25 am

*Mahi* wrote:Too much similarity with 2004 N3 in one problem.
Actually it's 2011 N3, the problem Zadid gave that is. :lol:
বড় ভালবাসি তোমায়,মা

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Family Of Functions

Unread post by *Mahi* » Wed Apr 17, 2013 2:28 pm

Tahmid Hasan wrote: Actually it's 2011 N3, the problem Zadid gave that is. :lol:
Knew that already :D i just commented on the uncanny similarity in the solution :mrgreen:
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: Family Of Functions

Unread post by asif e elahi » Fri Dec 20, 2013 1:53 pm

*Mahi* wrote:

If $f(x)$ is a solution to the given equation, then so is $f(x)+c$, so WLOG let $f(0)=0$.
Why f(0)=0 ?

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: Family Of Functions

Unread post by Fm Jakaria » Fri Dec 20, 2013 11:01 pm

@asif e elahi
To see this, suppose in such a solution f; f(x) = k. You may choose c = -k, so that in another solution g(x) = f(x) + c, g(x) = 0 holds.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply