# Polynomial $P(a)=b,P(b)=c,P(c)=a$

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.

• Are the integer coefficients positive or need not be? – user17762 May 10 '13 at 16:05
• It would be too easy – gukoff May 10 '13 at 16:06
• Since there was no such condition given in the question I guess they need not be positive. – Shaswata May 10 '13 at 16:06
• @Il It's a more precise way of stating it. "Different" could instead possibly mean "not all are equal", compare "coprime" vs. "pairwise coprime". – Bill Dubuque Jan 28 '15 at 17:11
• math.stackexchange.com/questions/806322/… – user263326 Aug 4 '16 at 20:44

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

• Then we can do it using contradiction.Thanks a lot! – Shaswata May 10 '13 at 16:16
• You are welcome. There are still a few lines to write, and one has to be careful. – André Nicolas May 10 '13 at 16:22

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.

• You may want to add that the lemma follows from the identity: $$a^k-b^k=(a-b)\sum_{\ell=0}^{k-1}a^\ell b^{k-\ell-1}.$$ – C. Falcon Dec 17 '16 at 17:14
• @C.Falcon Thank You added. – Taha Akbari Dec 17 '16 at 17:17
• You can't just assume that $a>b>c$ in the end; other cases should be checked as well – rabota Jan 21 '17 at 11:42
• @barto because it has the same calculation I didn't bring them. – Taha Akbari Jan 21 '17 at 13:37
• @TahaAkbari No. You seem to assume that $a>b>c$ up to cyclic permutation (which indeed gives the same system), whereas e.g. the case $b>a>c$ gives the substantially different $b-c=b-a=a-c$. (I'm not denying they're trivial to check, merely remarking upon the error of saying "Wlog, let $a>b>c$.") – rabota Jan 21 '17 at 13:44

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.

• I don't know how to bite that – I I Jan 28 '15 at 20:33
• @II What divisibility statements do you have available to chain into a cycle? – Bill Dubuque Jan 28 '15 at 20:37
• I don't know what is chaining into a cycle – I I Jan 28 '15 at 20:50
• @II A divisibility cycle looks like this $\ \color{#c00}j\mid k\mid n\mid \color{#c00} j\,\$ (view them as a circle / cycle, since they cycle back to the original number). – Bill Dubuque Jan 28 '15 at 20:57
• can you show me exactly how does it look like? – I I Jan 28 '15 at 21:04

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)

• Why should $p(p(p(a))) = a$ mean that $p(a) = a$? Note that $p(x) = \frac{1}{2}(-3x^2 + 11x - 4)$ has $p(p(p(1))) = 1$, it just doesn't have integer coefficients. – Ben Millwood Dec 17 '16 at 17:56
• @BenMillwood if $p(p(p(x)))=x$ for all $x$, then by observing the degree of the polynomial and trivially remaining cases, one has $p(x)=x$. Not sure what to do if it doesn't hold for all $x$ though. – Simply Beautiful Art Dec 17 '16 at 19:10
• @SimpleArt In this case it is only known that $p(p(p(x)))=x$ is true for three distinct $x$, namely $a,b,c$, not for all $x$, though you seem to understand it. – user236182 Dec 17 '16 at 19:51
• This answer needs editing. It is not clear how one concludes that $p$ is identity. To be honest, this is the same idea I had when I first read the question, but I don't see that it works, actually. From what is written, one can conclude that $(\deg p)^3 \geq 3$ but it needs clarification why this doesn't hold. – Ennar Dec 18 '16 at 9:20

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$