23
$\begingroup$

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.

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

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

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

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.

$\endgroup$
  • $\begingroup$ 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}.$$ $\endgroup$ – C. Falcon Dec 17 '16 at 17:14
  • $\begingroup$ @C.Falcon Thank You added. $\endgroup$ – Taha Akbari Dec 17 '16 at 17:17
  • $\begingroup$ You can't just assume that $a>b>c$ in the end; other cases should be checked as well $\endgroup$ – rabota Jan 21 '17 at 11:42
  • $\begingroup$ @barto because it has the same calculation I didn't bring them. $\endgroup$ – Taha Akbari Jan 21 '17 at 13:37
  • $\begingroup$ @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$.") $\endgroup$ – rabota Jan 21 '17 at 13:44
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't know how to bite that $\endgroup$ – I I Jan 28 '15 at 20:33
  • $\begingroup$ @II What divisibility statements do you have available to chain into a cycle? $\endgroup$ – Bill Dubuque Jan 28 '15 at 20:37
  • $\begingroup$ I don't know what is chaining into a cycle $\endgroup$ – I I Jan 28 '15 at 20:50
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Jan 28 '15 at 20:57
  • $\begingroup$ can you show me exactly how does it look like? $\endgroup$ – I I Jan 28 '15 at 21:04
0
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Ben Millwood Dec 17 '16 at 17:56
  • $\begingroup$ @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. $\endgroup$ – Simply Beautiful Art Dec 17 '16 at 19:10
  • $\begingroup$ @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. $\endgroup$ – user236182 Dec 17 '16 at 19:51
  • $\begingroup$ 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. $\endgroup$ – Ennar Dec 18 '16 at 9:20
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.