XXIX OM - I - Zadanie 9

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Udowodnić, że z każdego ciągu liczb naturalnych można wybrać podciąg, którego każde dwa wyrazy są względnie pierwsze, lub podciąg, którego wszystkie wyrazy mają wspólny dzielnik większy od 1.

Rozwiązanie

Niech $p$ będzie ustaloną liczbą pierwszą. Jeżeli nieskończenie wiele wyrazów ciągu jest podzielnych przez $p$ , to wyrazy podzielne przez $p$ tworzą podciąg, którego wszystkie wyrazy mają wspólny dzielnik większy od $1$ .

Rozpatrzmy więc przypadek, gdy dla każdej liczby pierwszej $p$ tylko skończona liczba wyrazów ciągu jest podzielna przez $p$ . Wtedy określamy indukcyjnie podciąg $b_1, b_2,\ldots$ danego ciągu, jak następuje. Jako $b_1$ bierzemy pierwszy wyraz danego ciągu. Jeżeli już zostały wybrane wyrazy $b_1, b_2, \ldots , b_n$ podciągu tak, że każde dwa z nich są względnie pierwsze, to jako $b_{n+1}$ bierzemy taki wyraz danego ciągu, który nie jest podzielny przez żaden czynnik pierwszy liczby $b_1b_2 \ldots b_n$ . Wtedy oczywiście liczba $b_{n+1}$ będzie względnie pierwszą z każdą z liczb $b_1, b_2, \ldots, b_n$ . Wobec tego na mocy zasady indukcji istnieje podciąg nieskończony $b_1, b_2, \ldots$ , którego każde dwa wyrazy są względnie pierwsze.