Udowodnić, że jeśli \(\displaystyle{ n}\) jest dowolną liczbą naturalną to istnieje liczba całkowita \(\displaystyle{ x}\) o tej własności, że każdy element zbioru \(\displaystyle{ \{ x^i + i \ , \ i=1,..., n \ \}}\) ma co najmniej \(\displaystyle{ 2^{n+1}}\) dzielników naturalnych
Udowodnimy dwa lematy. Niech \(\displaystyle{ \mathbb{P}}\) oznacza zbiór liczb pierwszych. Lemat 1.Niech \(\displaystyle{ f(x)\in \mathbb{Z}[x]}\) będzie wielomianem o najstarszym współczynniku dodatnim. Wówczas istnieje nieskończenie wiele \(\displaystyle{ p\in \mathbb{P}}\) takich, że kongruencja \(\displaystyle{ f(x)\equiv 0\, (\mathrm{mod}\,p)}\)
ma rozwiązanie. Dowód. Wielomian \(\displaystyle{ f(x)}\) o najstarszym współczynniku dodatnim potraktowany jako funkcja zmiennej rzeczywistej jest ściśle rosnący na pewnym przedziale \(\displaystyle{ (a,+\infty)}\). Stąd wynika, że ciąg \(\displaystyle{ \{f(n)\}_{n\in \mathbb{N}\cap (a,+\infty)}}\) rośnie w tempie wielomianowym. Z drugiej strony gdyby istniało tylko skończenie wiele \(\displaystyle{ p\in \mathbb{P}}\) takich, że kongruencja \(\displaystyle{ f(x)\equiv 0\, (\mathrm{mod}\,p)}\)
ma rozwiązanie, to istniałoby skończenie wiele liczb pierwszych, na które rozkładałby się każdy wyraz ciągu rosnącego \(\displaystyle{ \{f(n)\}_{n\in \mathbb{N}\cap (a,+\infty)}}\). W szczególności ciąg \(\displaystyle{ \{f(n)\}_{n\in \mathbb{N}\cap (a,+\infty)}}\) rósłby w tempie wykładniczym. To dawałoby sprzeczność.
Lemat 2.Niech \(\displaystyle{ f(x)\in \mathbb{Z}[x]}\) oraz niech \(\displaystyle{ m_1}\), \(\displaystyle{ m_2}\),...,\(\displaystyle{ m_n}\) będą liczbami całkowitymi parami względnie pierwszymi. Załóżmy, że kongruencje \(\displaystyle{ f(x)\equiv 0\,(\mathrm{mod}\,m_i)}\)
mają rozwiązania dla \(\displaystyle{ 1\leq i\leq n}\). Wówczas kongruencja \(\displaystyle{ f(x)\equiv 0\,(\mathrm{mod}\,m_1\cdot m_2\cdot...\cdot m_n)}\)
też ma rozwiązanie. Dowód. Niech \(\displaystyle{ r_i}\) będzie liczbą całkowitą taką, że \(\displaystyle{ m_i|f(r_i)}\) dla \(\displaystyle{ 1\leq i\leq n}\). Z chińskiego twierdzenia o resztach istnieje liczba całkowita \(\displaystyle{ r}\) taka, że \(\displaystyle{ r\equiv r_i\,(\mathrm{mod}\,m_i)}\)
dla \(\displaystyle{ 1\leq i\leq n}\). Wówczas \(\displaystyle{ f(r)\equiv f(r_i)\equiv 0\,(\mathrm{mod}\,m_i)}\)
Z tego, że liczby \(\displaystyle{ m_i}\) są parami względnie pierwsze dla \(\displaystyle{ 1\leq i\leq n}\) dostajemy \(\displaystyle{ f(r)\equiv 0\,(\mathrm{mod}\,m_1\cdot m_2\cdot...\cdot m_n)}\)
Ustalmy \(\displaystyle{ n\in \mathbb{N}}\). Załóżmy, że \(\displaystyle{ f_1(x)}\), \(\displaystyle{ f_2(x)}\),...,\(\displaystyle{ f_n(x)}\) są wielomianami o współczynnikach całkowitych i najstarszych współczynnikach dodatnich.
Dla każdego \(\displaystyle{ 1\leq i\leq n}\) niech \(\displaystyle{ \mathbb{P}_i}\) będzie zbiorem \(\displaystyle{ (n+1)}\)-różnych liczb pierwszych takich, że \(\displaystyle{ f_i(x)\equiv 0\,(\mathrm{mod}\,p)}\)
dla \(\displaystyle{ p\in \mathbb{P}_i}\). Ponadto niech \(\displaystyle{ \mathbb{P}_1}\),\(\displaystyle{ \mathbb{P}_2}\),...,\(\displaystyle{ \mathbb{P}_n}\) będą parami rozłączne. Istnienie takich zbiorów wynika natychmiast z Lematu 1. Niech \(\displaystyle{ m_i=\prod_{p\in \mathbb{P}_i}p}\)
dla \(\displaystyle{ 1\leq i\leq n}\). Na mocy Lematu 2 istnieje rozwiązanie kongruencji \(\displaystyle{ f_i(x)\equiv 0\,(\mathrm{mod} \,m_i )}\)
dla \(\displaystyle{ 1\leq i\leq n}\). Niech \(\displaystyle{ r_i}\) będzie liczbą całkowita taką, że \(\displaystyle{ m_i|f_i(r_i)}\) dla \(\displaystyle{ 1\leq i\leq n}\). Z chińskiego twierdzenia o resztach istnieje liczba całkowita \(\displaystyle{ r}\) taka, że \(\displaystyle{ r\equiv r_i\,(\mathrm{mod}\,m_i)}\)
Stąd \(\displaystyle{ f_i(r)\equiv f_i(r_i)\equiv 0\,(\mathrm{mod}\,m_i)}\). Wykazaliśmy, że istnieje liczba całkowita \(\displaystyle{ r}\) taka, że \(\displaystyle{ f_i(r)}\) ma \(\displaystyle{ (n+1)}\) różnych dzielników pierwszych dla każdego \(\displaystyle{ 1\leq i\leq n}\). Stąd \(\displaystyle{ f_i(r)}\) ma przynajmniej \(\displaystyle{ 2^{n+1}}\) różnych dzielników dla \(\displaystyle{ 1\leq i\leq n}\).
