[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2709
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 154 razy
Pomógł: 649 razy

Re: [Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: Sylwek » 8 lis 2019, o 02:14

Premislav pisze:
21 wrz 2019, o 20:30
Niech \(\displaystyle{ p\ge 5}\) będzie liczbą pierwszą. Niechaj \(\displaystyle{ N=(p-1)^{p}+1}\) i niech
\(\displaystyle{ N=\prod_{i=1}^{n}p_i^{\alpha_i}}\) (rozkład \(\displaystyle{ N}\) na czynniki pierwsze). Proszę wykazać, że
\(\displaystyle{ \sum_{i=1}^{n}\alpha_{i}p_{i}\ge \frac{p^{2}}{2}}\)
Przy \(\displaystyle{ p \ge 5}\) liczba \(\displaystyle{ N=(p-1)^p+1}\) jest nieparzysta i z racji \(\displaystyle{ p-1\equiv 0 \ (mod \ 3)}\) lub \(\displaystyle{ p-1\equiv 1 \ (mod \ 3)}\), nasza liczba \(\displaystyle{ N}\) jest też niepodzielna przez \(\displaystyle{ 3}\).

Pokażemy, że liczba \(\displaystyle{ N}\) ma w swoim rozkładzie jedynie czynniki pierwsze \(\displaystyle{ \ge p}\). Swoją drogą - bardzo ciekawy fakcik, nie spodziewałem się tego, ale Wolfram mnie naprowadził po przeliczeniu kilku przykładów.

Przypuśćmy nie wprost, że nasza liczba ma dzielnik pierwszy \(\displaystyle{ q \ge 5}\), przy czym \(\displaystyle{ q<p}\). Przy okazji wiemy, że \(\displaystyle{ q-1<q<p-1<p}\).

Zachodziłoby wtedy \(\displaystyle{ (p-1)^p \equiv -1 \ (mod \ q)}\). Jeśli \(\displaystyle{ q|(p-1)}\), to oznaczałoby to \(\displaystyle{ 0 \equiv -1 \ (mod \ q)}\), co daje sprzeczność. Zatem \(\displaystyle{ p-1}\) i \(\displaystyle{ q}\) są względnie pierwsze.

Niech \(\displaystyle{ t}\) będzie najmniejszą dodatnią liczbą całkowitą taką, że \(\displaystyle{ (p-1)^t \equiv -1 \ (mod \ q)}\). Taka liczba istnieje, bo zachodzi \(\displaystyle{ (p-1)^p \equiv -1 \ (mod \ q)}\).

Wtedy rzędem \(\displaystyle{ (p-1)}\) modulo \(\displaystyle{ q}\) jest liczba \(\displaystyle{ 2t}\) (znany fakcik, chętni sobie sprawdzą na marginesie). Ponadto \(\displaystyle{ (p-1)^{2p} \equiv 1 \ (mod \ q)}\), stąd \(\displaystyle{ 2t|2p}\) (fakcik z rzędów), czyli \(\displaystyle{ t|p}\) (można było do tego dojść "z samych minus jedynek", ale wolałem pojechać klasyką). Stąd \(\displaystyle{ t=1}\) lub \(\displaystyle{ t=p}\).

Ale pamiętając o MTF mamy \(\displaystyle{ t < 2t \le q-1 < p}\), stąd \(\displaystyle{ t=1}\), ale to oznacza \(\displaystyle{ (p-1)^1 \equiv -1 \ (mod \ q)}\), czyli \(\displaystyle{ q|p}\) - ta sprzeczność kończy nasz dowód nie wprost.

Udowodniliśmy więc, że liczba \(\displaystyle{ N}\) ma w swoim rozkładzie jedynie czynniki pierwsze \(\displaystyle{ \ge p}\). Teraz już będzie gładko do tezy. Zrobiłem to na dwa sposoby, pierwszy poprzez "przypadek najtrudniejszy" typu \(\displaystyle{ p^{\log_p N}}\), drugi przez luźne szacowania w \(\displaystyle{ 2}\) przypadkach.

Mamy \(\displaystyle{ p^{\log_p N}=N=\prod p_i^{\alpha_i}=p^{\log_p \prod p_i^{\alpha_i}} = p^{\sum \alpha_i \log_p p_i}}\).

Pokażemy, że \(\displaystyle{ \sum \alpha_i p_i \ge p \cdot \sum \alpha_i \log_p p_i}\). Aby to udowodnić, wystarczy pokazać, że \(\displaystyle{ p_i \ge p \cdot \log_p p_i}\), co jest równoważne \(\displaystyle{ p^{p_i} \ge p_i^p}\), lub jak ktoś woli \(\displaystyle{ \frac{\ln p}{p} \ge \frac{\ln p_i}{p_i}}\). A to jest prawdą na mocy tego, że pochodne szybko wskazują, że funkcja \(\displaystyle{ f(x)=\frac{\ln x}{x}}\) maleje na przedziale \(\displaystyle{ [e, \infty)}\), a u nas jest przecież \(\displaystyle{ e < 5 \le p \le p_i}\).

Dostajemy stąd ekspresowo: \(\displaystyle{ \sum \alpha_i p_i \ge p \cdot \sum \alpha_i \log_p p_i = p \cdot \log_p N}\), więc aby pokazać tezę, wystarczy pokazać, że \(\displaystyle{ \log_p N \ge \frac{p}{2}}\), czyli \(\displaystyle{ N^2 > p^p}\), a to jest jasne, bo \(\displaystyle{ N^2 > (p-1)^{2p}=(p^2-2p+1)^p = (p(p-3)+p+1)^p > p^p}\).

Jak już dorżnąłem to zadanko, to zrozumiałem, że szacowanie jest na tyle grube, że można było też robić znacznie luźniej. A mianowicie tak. Jeśli \(\displaystyle{ N}\) ma jakiś dzielnik pierwszy \(\displaystyle{ \ge \frac{p^2}{2}}\), to zadanie jest oczywiście skończone. Jeśli nie, to podsumowując nasze wnioski, wiemy, że wszystkie dzielniki pierwsze \(\displaystyle{ N}\) są w zbiorze \(\displaystyle{ \left[p, \frac{p^2}{2} \right)}\). Ale wtedy prawdopodobnie okaże się, że tych dzielników (licząc wraz z krotnościami) jest dużo, tzn. co najmniej \(\displaystyle{ \frac{p}{2}}\). Oczywiście to też zakończyłoby dowód, bo wtedy \(\displaystyle{ \sum \alpha_i p_i \ge \sum \alpha_i p = p \cdot \sum \alpha_i \ge p \cdot \frac{p}{2} = \frac{p^2}{2}}\).

Pokażemy więc, że naprawdę naszych dzielników jest co najmniej \(\displaystyle{ \frac{p}{2}}\). Gdyby tak nie było (tzn. byłoby ich mniej niż \(\displaystyle{ \frac{p}{2}}\), licząc wraz z krotnościami), to \(\displaystyle{ N=\prod p_i^{\alpha_i} < \left(\frac{p^2}{2}\right)^{\frac{p}{2}}}\). Ale pokażemy, że \(\displaystyle{ N > \left(\frac{p^2}{2}\right)^{\frac{p}{2}}}\), co jest łatwe, bo wystarczy pokazać, że \(\displaystyle{ (p-1)^p > \left(\frac{p^2}{2}\right)^{\frac{p}{2}}}\). Jest to równoważne \(\displaystyle{ (p-1)^2> \frac{p^2}{2}}\), czyli \(\displaystyle{ p^2-4p+2>0}\), a przy \(\displaystyle{ p \ge 5}\) oczywiście \(\displaystyle{ p^2-4p=p(p-4)>0}\), co kończy dowód.

---

Kolejne zadanko.
Nie chce mi się szukać ani wymyślać, więc dam takie jedno krótkie na czytanie ze zrozumieniem tego, co napisałem powyżej. Myślę, że umiejętność zrozumienia czyjegoś rozwiązania również jest bardzo ważna przy nauce do OM, więc chyba w sam raz na temat "Rozgrzewka OM" ;-)

Niech \(\displaystyle{ p\ge 5}\) będzie liczbą pierwszą. Niechaj \(\displaystyle{ N=(p-1)^{p}+1}\) i niech
\(\displaystyle{ N=\prod_{i=1}^{n}p_i^{\alpha_i}}\) (rozkład \(\displaystyle{ N}\) na czynniki pierwsze). Proszę wykazać, że
\(\displaystyle{ \sum_{i=1}^{n}\alpha_{i}p_{i}\ge p^2 \cdot \log_p (p-1)}\)

ODPOWIEDZ