XXX OM - II - Zadanie 5

Udowodnić, że wśród każdych dziesięciu kolejnych liczb naturalnych istnieje taka, która jest względnie pierwsza z każdą z pozostałych dziewięciu.

Rozwiązanie

Każdy wspólny dzielnik dwóch liczb naturalnych jest też dzielnikiem ich różnicy. Jeżeli więc spośród dziesięciu kolejnych liczb naturalnych pewne dwie nie są względnie pierwsze, to mają wspólny dzielnik będący liczbą pierwszą mniejszą od $ 10 $, tzn. jedną z liczb $ 2 $, $ 3 $, $ 5 $, $ 7 $.

Wśród dziesięciu kolejnych liczb naturalnych jest pięć nieparzystych. Wśród tych pięciu liczb nieparzystych co najwyżej dwie są podzielne przez $ 3 $, jedna podzielna przez $ 5 $ i co najwyżej jedna podzielna przez $ 7 $. Pozostaje więc co najmniej jedna liczba nie podzielna przez żadną z liczb $ 2 $, $ 3 $, $ 5 $, $ 7 $. Jest więc ona względnie pierwsza z każdą z pozostałych dziewięciu.

Uwaga. Analogiczne zadanie było zadaniem konkursowym 14(2) na zawodach II stopnia V Olimpiady Matematycznej.

Komentarze

Dodaj nową odpowiedź