XXXVI OM - III - Zadanie 1

Zawody matematyczne:

XXXVI OM, 1984-1985

Etap:

III

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$ .