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}\).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}}\)
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)}\)