Interesting equation $P(x)=Q(y)$, with infinite integer solutions $(x,y)$ 
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 equation has an infinite number of answers in $\mathbb{N} \times \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 $gcd(deg(P),deg(Q))=1$.

The two problems are originated from the 2013 Iranian Math Olympiad, 3rd Round. I have not been able to solve any of the problems, and I cannot find the solutions elsewhere.  
Here is my current sketch for problem a. :
Step 1: Suppose that $S$ is an answer of infinitely many interesting equations, including the two interesting equations $P(x)=Q(y)$ and $F(x)=G(y)$.
Lemma 1.1: Without loss of generality assume that the leading coefficients of $P$ and $F$ are positive integers. Then the leading coefficients of $Q$ and $G$ must also be positive integers.


*

*If not, then $\lim Q(y) = - \infty$, $\lim P(x) = + \infty$, so the equation has a finite number of answers in $\mathbb{N} \times   
   \mathbb{N}$, a contradiction.


Lemma 1.2: Without loss of generality assume that $deg(P) \leq deg(Q)$. Then $deg(F)$ must be less than or equal to $deg(G)$.


*

*Since $deg(P) \leq deg(Q)$, there are infinite answers $(x, y)$ in $S$, such that $x < y$. Therefore, since $F(x)=G(y)$ has infinite solutions $(x, y)$ in $S$, $deg(F)$ must be less than or equal to $deg(G)$
Lemma 1.3: Without loss of generality assume that $deg(P) \leq deg(Q)$ and  $deg(P) \leq deg(F)$. Then  $deg(P) < deg(F)$ if and    only if $deg(Q) < deg(G)$. Moreover $deg(P) = deg(F)$ if and only if    $deg(Q) = deg(G)$.


*

*Consider the case in which $deg(P) < deg(F)$.

*If $deg(Q) > deg(G) \geq deg(F) > deg(P)$ then the leading coefficient of $F-P$ is positive, while the leading coefficient of $G-Q$ is negative. This contradicts Lemma 1.1 (Note that $S$ is also an answer of the interesting equation $F(x)-P(x)=G(y)-Q(y)$).

*If $deg(Q) = deg(G)$, then the leading coefficient of $F-aP$ is positive, while the leading coefficient of $G-aQ$ is negative ($a$ is the positive integer such that the leading coefficient of $aQ$ is greater than $G$'s). This also contradicts Lemma 1.1 (Note that $S$ is an answer of the interesting equation $F(x)-aP(x)=G(y)-aQ(y)$).

*Therefore $deg(P) < deg(F)$ if and only if $deg(Q) < deg(G)$.

*With arguments similar to the above, it can be proven that $deg(P) = 
   deg(F)$ if and only if $deg(Q) = deg(G)$.
Lemma 1.4: $\frac{deg(P)}{deg(Q)}=\frac{deg(F)}{deg(G)}$, regardless of whether $deg(P)$ is less than $deg(Q)$, $deg(F)$ or not.


*

*Note that $S$ is the answer of the interesting equations $P^{deg(F)}(x)=Q^{deg(F)}(y)$ and $F^{deg(P)}(x)=G^{deg(P)}(y)$. 

*Thus according to Lemma 1.3 , $deg(Q^{deg(F)}) =
   deg(G^{deg(P)})$; in other words, $deg(Q) \times deg(F) = deg(P)
   \times deg(G)$, or $\frac{deg(P)}{deg(Q)}=\frac{deg(F)}{deg(G)}$.


Step 2: Lemma 2: Assume that $P(x)=Q(y)$ is the equation with the smallest degree, of all equations of which $S$ is the answer. Then $deg(P)|deg(F)$ and $deg(Q)|deg(G)$


*

*I wasn't able to prove Lemma 2. But if problem b. is proven,
then Lemma 2 might be able to be proven with the similar techniques.


Step 3: Lemma 3: If $deg(P)|deg(F)$ and $deg(Q)|deg(G)$, then $P(x)=Q(y)$ yields in the equation $F(x)=G(y)$ (With definition of $P,Q,F,G$ similar to Step 1 and 2).


*

*Let $k = \frac{deg(F)}{deg(P)} = \frac{deg(G)}{deg(Q)} $. Let $p,q,f,g$ be the leading coefficient of $P,Q,F,G$ respectively, and without loss of generality assume that $gcd(p,q)=gcd(f,g)=1$. It can be seen that ${f} \times P^k(x)={f}\times Q^k(y)$ and ${p^k} \times F(x)={p^k}\times G(y)$ are interesting equations, and according to Lemma 1.3, it can be proven that $f = p^k, g = q^k$. Therefore $$U(x) = {f} \times P^k(x) - {p^k} \times F(x) = {f}\times Q^k(y) - {p^k}\times G(y) = V(y)$$ is an interesting equation, with $deg(U) < deg(F)$ and $deg(V) < deg(G)$. From Lemma 2, it can be seen that 
$deg(P)|deg(U)$ and $deg(Q)|deg(V)$.

*Continuing the process similar to the above by changing $F$ with $U$, $G$
with $V$, with the fact that $S$ is also the answer of $U(x)=V(y)$, it can be achieved that $P(x)=Q(y)$ yields in $F(x)=G(y)$, and problem a. is solved.
To conclude, here are my questions:

How can I solve the two original problems ? 
Can I solve them using my ideas above ? 
If a solution or the question has been posted, please let me know.

Any suggestions, answers, comments, edits will be appreciated.
 A: This is a full solution for a.
Let $S$ be an infinite subset of $\mathbb{N}^2$ and $P(x)=Q(y)$ be an interesting equation for which $S$ is an answer. 
Write $S=\{(x_i,y_i)|i \geq 1\}$ any enumeration. 
So we have $P(x_i)=Q(y_i)$. Assume $y_{\varphi(i)}$ is constant: then $P(x_{\varphi(i)})$ is constant, so since $x_{\varphi(i)}$ is injective, $P$ is constant, a contradiction. 
So (similarly) $x_i$ and $y_i$ both go to infinity. 
Let then $p$ be the degree of $P$ ($\alpha$ the dominant coefficient), $q$ be the degree of $Q$ ($\beta$ the dominant coefficient), then $\frac{P(x_i)}{\alpha x_i^p}$ and $\frac{Q(y_i)}{\beta y_i^q}$ go to $1$ as $i$ goes to infinity. 
Therefore, $\frac{\alpha}{\beta}\frac{x_i^p}{y_i^q}$ goes to $1$ as $i$ goes to infinity. 
This shows that $\alpha$ and $\beta$ have the same sign, and that $p/q$, $(|\alpha|/|\beta|)^{1/q}$ have to be constants (say, $r$ and $\delta$), depending only on $S$ (and more precisely on any infinite subset of $S$)
So assume now that $P(x)=Q(y)$ is an interesting equation with answer any cofinite subset of $S$ such that the degree of $Q$ is minimal. 
Let $P_1(x)=Q_1(y)$ be an interesting equation with answer a cofinite subset of $S$ such that $P(x)=Q(y)$ does not yield to it, such that $Q_1$ has minimal degree (and among these, such that $|\alpha|+|\beta|$ is minimal). 
If $Q_1$ and $Q$ have the same degree, then so do $P_1$ and $P$, and by the above (with the same notations) $(\alpha_1,\beta_1)$ and $(\alpha,\beta)$ are proportional: let $c,c_1$ be nonzero integers such that $c_1\alpha_1=c\alpha$ (same for $\beta$).
Then $(cP-c_1P_1,cQ-c_1Q_1)$ has a cofinite subset of $S$ as an answer, and a lower degree, so it cannot be interesting and thus the polynomials are constants, so $(P,Q)$ yields in $(P_1,Q_1)$, a contradiction. 
So $Q_1$ has a higher degree than $Q$. Let us write Euclidean divisions in $\mathbb{Q}[X]$, $P_1=A_1P+A_2$, $Q_1=B_1Q+B_2$. Up to multiplication by an integer constant, we may assume that all the polynomials have integer coefficients. 
So we have on a cofinite subset of $S$, $(A_1(x_i)-B_1(y_i))P(x_i)=A_2(x_i)-B_2(y_i)$. 
Since $A_2,B_2$ have lower degrees than $P,Q$, $A_2(x_i)$ and $B_2(y_i)$ are negligible before $P(x_i)=Q(y_i)$. So their difference is negligible before $(A_1(x_i)-B_1(y_i))P(x_i)$ (on the subset of $i$ such that $A_1(x_i) \neq B_1(y_i)$). 
As a conclusion, on a cofinite subset of $S$, $A_1(x_i)=B_1(y_i)$ and thus $A_2(x_i)=B_2(y_i)$. By minimality of $P,Q$, $A_2$ and $B_2$ are constants, and $A_1,B_1$ (by mininality of $P_1,Q_1$) are yielded in by $P,Q$. We get a contradiction. 
