I. megoldás. Megmutatjuk, hogy létezik a megfelelő tulajdonságú polinom. Adott $f\left(x\right)$ polinomra jelölje a $k$-szorosan összetett $f\left(f\left(\text{...}f\left(x\right)\text{...}\right)\right)$ polinomot $f_k\left(x\right)$. Ekkor elegendő, ha tetszőleges $k$-ra $m$ és $f_k\left(m\right)$ minden $m$ egészre relatív prímek, hiszen a feladat sorozatának bármely két tagja ilyen alakú.
Ha $m=f\left(0\right)$, a polinom konstans tagja, akkor $f\left(m\right)$ többszöröse $m$-nek. Ha a konstans tagot 1-nek választjuk, akkor ezzel annyit legalábbis elérünk, hogy $\left(m;f\left(m\right)\right)=1$ teljesüljön minden $m$ egészre, mégpedig úgy, hogy $f\left(m\right)=q\cdot m+1$, ahol $q$ egész szám.
Nézzük meg, mit kapunk, ha az $M=q\cdot m+1$ értéket helyettesítjük, azaz $f\left(f\left(m\right)\right)=f\left(M\right)$ értékét számoljuk ki. Ha $i>0$, akkor a binomiális tétel szerint ${\left(q\cdot m+1\right)}^i=q\text{'}\cdot m+1$, ahol $q\text{'}$ is egész szám. Tetszőleges egész együtthatós $f\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\text{...}+a_0$ polinomra tehát $f\left(M\right)=Q\cdot m+a_n+a_{n-1}+\text{...}+a_1+a_0$, ahol $Q$ egész szám. Ha tehát a polinom együtthatóinak az összegét, az $f\left(1\right)$ értéket is 1-nek választjuk, akkor $M=q\cdot m+1$-ből $f\left(M\right)=m\cdot Q+1$ következik. Innen pedig indukcióval nyomban adódik, hogy minden $k$-ra $f_k\left(m\right)=m\cdot Q_k+1$, ahol $Q_k$ egész szám.
Ilyenkor pedig $m$ és $f_k\left(m\right)$ valóban relatív prímek.
Feltételünk tehát $f\left(0\right)=f\left(1\right)=1$, ez pedig nyilván minden legalább másodfokú polinomra teljesíthető, egy 2003-adfokú megoldás $f\left(x\right)=x^{2003}-x+1$.