$P(x)\in\mathbb Z$ iff $Q(x)\in\mathbb Z$

Well I have a problem on polynomial, it said like that: Let $P,Q$ be polynomials with real coefficients (that is $P,Q\in\mathbb R[x]$). We assume that for every $x\in\mathbb R$ then $P(x)\in \mathbb Z$ if and only if $Q(x)\in\mathbb Z$. I need to prove that $P+Q$ or $P-Q$ must be constant. How could we prove this?

• If this is contest math, would you mind adding the source? – tomasz Jul 30 '13 at 2:17
• My friend said it is in some shortlist of IMO but I do not exactly where it is. – Hai Minh Jul 30 '13 at 2:25

Another approach to this question is to think of the map $x \mapsto (P(x),Q(x))$ as a polynomial curve in the $(x,y)$-plane. The condition that $P(x)$ is integral iff $Q(x)$ is integral means that this curve only ever crosses the vertical lines $x =$ an integer or the horizontal lines $y =$ an integer at the intersection points of those lines.

As in tomasz's answer, scaling one or both of $P$ or $Q$ by $-1$ if necessary we may assume that $P(x)$ and $Q(x)$ are both increasing if $x$ is large enough, so our curve is wandering off to infinity in the $(x,y)$-plane in roughly the north-east direction'', so to speak.

Now think about what happens when this curve enters one of the integral lattice squares, and then exits it. What are the possible entry/exit points? (If you can't visualize this just by reading it, draw a picture.)

At this point these hints merge completely with those of tomasz: you will an infinite sequence of $x$ values such that $P(x) = Q(x) +$ a constant , and thus deduce that $P(x) = Q(x) +$ a constant.

(So basically, this is a slightly more geometric way of thinking about tomasz's series of hints.)

A few hints to guide you to a solution.

The case when $P,Q$ are constant is trivial. Suppose they're not constant.

First, we can assume without loss of generality that they're both increasing starting at $0$ by shifting both and/or multiplying one or both by $-1$ if necessary. Why can we do that?

Not only that, we can assume in addition that $P(0)=Q(0)=0$ with a similar trick. Why?

From that, we can deduce that, in fact, for infinitely many $x>0$, $P(x)=Q(x)$. How?

What can you say about two polynomials that agree on an infinite set?

• Very nice answer. You successfully hint at the fun part of the argument without giving it away. – Dan Jul 30 '13 at 2:38
• @Dan: Thanks. :) If you like my answer, feel free to upvote it. – tomasz Jul 30 '13 at 2:41
• Whoops! Thought I did. I've fixed that. :) – Dan Jul 30 '13 at 2:42
• Could you write down the solution in details? – Hai Minh Jul 30 '13 at 2:52
• @user80121: I could, but I'd rather you tried to follow the steps. – tomasz Jul 30 '13 at 2:56