Rõ ràng \(\deg (P) > 0.\) Đặt \(\deg (P) = m\) và a là hệ số bậc cao nhất của P, không mất tổng quát, coi a > 0.

Gọi \(x_n\) là nghiệm nguyên lớn nhất của phương trình \(P\left( x \right) = {2^n}\)

Dễ thấy \(\lim {x_n} =  + \infty \) nên \(\lim \frac{{ax_n^m}}{{{2^n}}} = 1\) và do đó \(\lim \frac{{{x_{n + 1}}}}{{{x_n}}} = \sqrt[m]{2}\)

Hơn nữa, do \({x_{n + 1}} - {x_n}\) là ước của \(P\left( {{x_{n + 1}}} \right) - P\left( {{x_n}} \right)\) nên \({x_{n + 1}} - {x_n} = {2^{{k_n}}}\) với \(k_n\) là số tự nhiên nào đó. Suy ra

\(\frac{{{x_{n + 1}}}}{{{x_n}}} = 1 + \frac{{{2^{{k_n}}}}}{{{x_n}}}\)

và \({\left( {\sqrt[m]{2} - 1} \right)^m} = \lim {\left( {\frac{{{2^{{k_n}}}}}{{{x_n}}}} \right)^m} = \lim \frac{{a{{.2}^{m.{k_n}}}}}{{ax_n^m}} = a.\lim {2^{m.{k_n} - n}}\)

Do đó, dãy \(\left( {m - {k_n} - n} \right)\) phải hội tụ đến l (nguyên) nào đó. Kéo theo \({\left( {\sqrt[m]{2} - 1} \right)^m} = a{.2^l}\). Do đó, m phải bằng 1.

Đặt \(P\left( x \right) = ax + b\). Từ \(a\left( {{x_2} - {x_1}} \right) = 2\) ta suy ra \(a =  \pm 1, \pm 2\). Từ đó, ta tìm được tất cả các đa thức P(x) thỏa mãn là \(P\left( x \right) = a\left( {x + k} \right)\) với \(a =  \pm 1, \pm 2\) và k là một số nguyên tùy ý.