XXXVI OM - III - Zadanie 1

Wyznaczyć największą liczbę $ k $ taką, że dla każdej liczby naturalnej $ n $ istnieje co najmniej $ k $ liczb naturalnych większych od $ n $, mniejszych od $ n+17 $ i względnie pierwszych z iloczynem $ n(n+17) $.

Rozwiązanie

Udowodnimy najpierw, że dla każdej liczby naturalnej $ n $ istnieje co najmniej jedna liczba naturalna zawarta między $ n $ i $ n+17 $ względnie pierwsza z $ n(n+17) $.

W przypadku, gdy $ n $ jest liczbą parzystą, wymaganą własność ma liczba $ n+1 $. Oczywiście liczby $ n $ i $ n+1 $ są względnie pierwsze. Gdyby liczba $ d > 1 $ była wspólnym dzielnikiem liczb $ n+1 $ i $ n+17 $, to dzieliłaby ona różnicę $ (n+17)-(n+1) = 16 $, a zatem byłaby liczbą parzystą. Ponieważ jednak $ n+1 $ jest liczbą nieparzystą, więc takie $ d $ nie istnieje. Wobec tego liczby $ n+1 $ i $ n(n+17) $ są względnie pierwsze.

W przypadku, gdy $ n $ jest liczbą nieparzystą, wymaganą własność ma liczba $ n + 16 $. Istotnie liczby $ n+16 $, $ n+17 $ są względnie pierwsze. Podobnie jak wyżej stwierdzamy, że $ n $ i $ n+16 $ również są względnie pierwsze. Zatem $ n+16 $ i $ n(n+17) $ są względnie pierwsze.

Udowodniliśmy w ten sposób, że $ k \geq 1 $.

Rozważmy liczbę $ n = 16! $. Liczby $ n+2, n+3, \ldots,n+16 $ nie są względnie pierwsze z $ n(n+17) $, gdyż dla $ j = 2, 3, \ldots, 16 $ liczby $ n+j $ i $ n $ dzielą się przez $ j $. Jedynie liczba $ n+1 $ jest względnie pierwsza z $ n(n+17) $. Z przykładu tego wynika, że $ k \leq 1 $. Ostatecznie więc $ k = 1 $.

Komentarze

Dodaj nową odpowiedź