Welcome to our community

Be a part of something great, join today!

Problem Of The Week # 288 - Nov 09, 2017

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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 POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
Congratulations to castor28 for his correct solution to the Putnam Archive Problem B-1 from 2007, which follows:

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)$.
 
Status
Not open for further replies.