XXIX OM - I - Zadanie 9

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.

Komentarze

Dodaj nową odpowiedź