Polynomials with integer coefficients such that $p(a)=b,p(b)=c,p(c)=a$ [duplicate]

Let $a,b,c$ be $3$ distinct integers, and let $P$ be a polynomial with integer coefficients.Show that in this case the conditions $$P(a)=b,P(b)=c,P(c)=a$$ cannot be satisfied simultaneously.

Any hint would be appreciated.

Solution 1:

Hint: If $P(a)=b$ and $P(b)=c$ then $a-b$ divides $b-c$.

Solution 2:

Lemma:If $P(x)$ is a polynomial with integer coefficients then $a-b \mid P(a)-P(b)$

Proof:Take $P(x)=a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_{1}x+a_0$

Then You cold easily prove the lemma by the identity $$a^k-b^k=(a-b)\sum_{\ell=0}^{k-1}a^\ell b^{k-\ell-1}$$

So we have:

$$b-c \mid a-b$$$$a-b \mid c-a$$ $$c-a \mid b-c$$

Which gives us $b-c \mid a-b \mid c-a \mid b-c$.

$$\Rightarrow \mid b-c \mid \ge \mid a-b \mid \ge \mid c-a \mid \ge \mid b-c \mid$$

then :

$\mid b-c \mid =\mid a-b \mid =\mid c-a \mid$

The problem is cyclic so without loss of generality we can take $a=max\{a,b,c\}$.So we have:

$a-b=a-c \Rightarrow b=c$

Which is wrong.

Solution 3:

Hint $\ a\!-\!b\mid P(a)\!-\!P(b) = b\!-\!c.\,$ By symmetry $\,b\!-\!c\mid c\!-\!a,\ \ c\!-\!a\mid a\!-\!b.\ $ Chained, these yield a divisibility cycle $\ \color{#c00}j\mid k\mid n\mid \color{#c00} j,\ $ so $\ k,n = \pm j.\ $ But $\,j+k+n = 0\,\Rightarrow\, j=0\,\Rightarrow\,a=b\,\Rightarrow\!\Leftarrow$

Remark $ $ The divisibility is a specialization of the Factor Theorem $\,x-b\mid P(x)-P(b)\,$ or the Polynomial Congruence Rule $\bmod a\!-\!b\!:\ a\equiv b\,\Rightarrow\, P(a)\equiv P(b),\ $ for $\,P\in\Bbb Z[x],\,$ see here

Note $\ $ This (accepted) answer was merged from here, so comments, votes, etc might not be in sync.

Solution 4:

As known, $p(a)=b$ $\implies p(b)=p(p(a))=c\implies p(c)=p(p(p(a)))=a$. Which implies that the polynomial is of the kind $p(x)=x$. So,we get $p(a)=a$ and we also know that $p(a)=c$. So $c=a$. A contradiction ($a,b,c$ are distinct)

Solution 5:

Very late reply, but as a proof I posted to this problem was marked as a duplicate to this one, I thought I would repost it as an answer here in the off-chance someone might find the reasoning useful. This proof does not assume the divisibility cycle theorem mentioned in other answers (actually, it shows how the specific case $n=3$ of the theorem can be derived).

Proof: Let $P(x)$ be a polynomial of degree $n$ with integer coefficients. Assume there exist three distinct integers $a,b, c$ such that $$P(a)=b, P(b)=c, P(c)=a.$$ Since the integers are distinct, there is a least among them. Without loss of generality, write $a<b$ and $a<c$.

Note that, for any two real numbers $x,y$, $$P(x)-P(y)=a_n(x^n - y^n)+a_{n-1}(x^{n-1}-y^{n-1})+ \cdots +a_1(x-y).$$

So, using the identity $$x^n -y^n=(x-y)(x^{n-1}+x^{n-2}y+ \cdots + xy^{n-2} + y^{n-1}),$$

it follows that $$P(x)- P(y)=(x-y)Q(x,y),$$ where $Q(x,y)$ is a polynomial in $x,y$, of degree $(n-1)$. Examining the properties of $Q$ will give us the contradiction we seek. Plugging the values $a,b$ into the above gives $$P(a)-P(b)=(a-b)Q(a,b)=b-c.$$

By our construction of $Q$, it is clear that, just as $P$, it too must have integer coefficients; and so we can write $Q(a,b)=m_1$, for some integer $m_1$. This same argument eventually gives the following three equations: $$\begin{align} \tag{1} (a-b)m_1=b-c \\ \tag{2}(b-c)m_2=c-a \\ \tag{3} (c-a)m_3=a-b \end{align} .$$

Since the integers $a,b,c$ are distinct, $m_i\neq 0$ for any $i$.

Next, divide (1) by (2):

$$\tag{1’} \frac{a-b}{c-a} m_1=\frac{1}{m_2}.$$

Dividing both sides of $(3)$ by $m_3$ and then taking the reciprocal gives:

$$\tag{3’} \frac{1}{c-a}=\frac{m_3}{a-b}.$$

Substituting $(3’)$ into $(1’)$ finally yields the following equation:

$$m_1 m_3=\frac{1}{m_2},$$

which means $m_i=\pm 1$ for all $i$. This implies $m_3=-1 \implies a-c=a-b \implies c=b$, which is a contradiction. $\quad \square$

Corollary 1: Let $j,k,l$ be integers such that ${\color{DarkRed}j }| k , k | l , l | {\color{DarkRed}j } $, then $k, l= \pm j$.

Proof: By definition $j m_1=k$, $km_2=l$,$lm_3=j$, and since we have shown in this case the $m_i= \pm 1$ for all $i$, the result follows. $\quad \square$

Corollary 2: Let $S=(a_1, a_2, \cdots, a_n)$ be any set of $n$ integers, $n\geq 2$, such that $$a_1 \mid a_2\mid \cdots \mid a_n \mid a_1,$$ then $a_i = \pm a_1$.

Proof: This is a straight-forward proof by induction. The case $n=2$ is just a simpler version of the proof for $n=3$ given above.

Next, is the inductive hypothesis. Assume that, for any set of $n-1$ integers which satisfy a division cycle, then $a_i=\pm a_1$ for all $i$, $1\leq i \leq n-1$. Next, assume there is a set S as above.

Since $a_{n-1}m_1=a_{n}$ and $a_n m_2=a_1$, it follows that $a_{n-1} \mid a_1$. Without loss of generality we can write $a_1\mid a_n \mid a_1 \implies a_n= \pm a_1$, which completes the proof. $\quad \square$