# Problem Of The Week # 288 - Nov 09, 2017

Status
Not open for further replies.

#### Ackbach

##### Indicium Physicus
Staff member
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.

-----

#### Ackbach

##### Indicium Physicus
Staff member
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.