IR-MO 2013 Problem 7

An equation $P(x)=Q(y)$ is called Interesting if $P$ and $Q$ are polynomials with degree at least one and integer coefficients and the equations has an infinite number of answers in $\mathbb{N}$ . An interesting equation $P(x)=Q(y)$ yields in interesting equation $F(x)=G(y)$ if there exists polynomial $R(x) \in \mathbb{Q} [x]$ such that $F(x) \equiv R(P(x))$ and $G(x) \equiv R(Q(x))$ . (a) Suppose that $S$ is an infinite subset of $\mathbb{N} \times \mathbb{N}$ . $S$ is an answer of interesting equation $P(x)=Q(y)$ if each element of $S$ is an answer of this equation. Prove that for each $S$ there's an interesting equation $P_0(x)=Q_0(y)$ such that if there exists any interesting equation that $S$ is an answer of it, $P_0(x)=Q_0(y)$ yields in that equation. (b) Define the degree of an interesting equation $P(x)=Q(y)$ by $max\{deg(P),deg(Q)\}$ . An interesting equation is called primary if there's no other interesting equation with lower degree that yields in it. Prove that if $P(x)=Q(y)$ is a primary interesting equation and $P$ and $Q$ are monic then $(deg(P),deg(Q))=1$ .

Time allowed for this question was 2 hours.