MathDB

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)

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.

Problem Statement