Problem Of The Week # 288 - Nov 09, 2017

[Ackbach]

Here is this week's POTW:

-----

Let $f$ be a polynomial with positive integer coefficients. Prove that if $n$ is a positive integer, then $f(n)$ divides $f(f(n)+1)$ if and only if $n=1$. Assume $f$ is non-constant.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to castor28 for his correct solution to the Putnam Archive Problem B-1 from 2007, which follows:

[sp]Since $f$ has integer coefficients, we have $f(k+1)\equiv f(1)\pmod{k}$ for any integer $k$. Taking $k=f(n)$, we get $f(f(n)+1)\equiv f(1)\pmod{f(n)}$. This means that we must prove that, if $n>0$, $f(n)\mid f(1)$ if and only if $n = 1$.

The "if" part is obvious. For the converse, note that, since $f$ has positive coefficients and is not constant, $f(x)$ is a strictly increasing function of $x$ for $x > 0$. In particular, if $n>1$, we have $f(n) > f(1) > 0$, and $f(n)$ cannot divide $f(1)$.[/sp]