Matematyka.pl

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

Świetne rozwiązanie, jakby kogoś interesowało, jest to zadanie 6b) z włoskiego TST z roku 2007.

Trochę szkoda, że nikt, dla kogo byłoby to pożytecznym ćwiczeniem, nie odezwał się w odpowiedzi, w każdym razie do nowego zadania wystarczy zastosować Sylwkową koncepcję nr 1, do momentu, w którym uzyskaliśmy szacowanie
\(\displaystyle{ \sum_{i=1}^{n}\alpha_{i}p_{i}\ge p\log_{p}N}\).
Dalej wystarczy udowodnić, że \(\displaystyle{ p\log_{p}N\ge p^{2}\log_{p}(p-1)}\), ale skoro \(\displaystyle{ N=(p-1)^{p}+1}\) i jak nietrudno stwierdzić, funkcja \(\displaystyle{ f(x)=\log_{p}x, \ p\in \PP}\) jest ściśle rosnąca, więc dostajemy
\(\displaystyle{ p\log_{p}N=p\log_{p}\left((p-1)^{p}+1\right)>p\log_{p}(p-1)^{p}=p^{2}\log_{p}(p-1)}\). Serio nic więcej tu nie było trzeba zmodyfikować?

To może teraz takie zadanko na rozgrzewkę:
proszę rozwiązać równanie w liczbach całkowitych dodatnich
\(\displaystyle{ m^{3}-n^{3}=7mn+5}\)

Tak, jest OK! Dokładnie o to mi chodziło

Co do Twojego zadania - skoro mamy rozwiązać to równanie w liczbach całkowitych dodatnich, to prawa strona jest większa od zera, zatem lewa też, a stąd \(\displaystyle{ m > n}\).

Mamy \(\displaystyle{ m^3-n^3=(m-n)(m^2+mn+n^2)=7mn+5}\). Ponieważ \(\displaystyle{ m>n}\), to \(\displaystyle{ m^2+mn+n^2=(m-n)^2+3mn>3mn}\).

Intuicja jest taka, że generalnie lewa strona zwykle mocno przebije prawą stronę, co zaraz szybko udowodnimy.

Gdyby więc \(\displaystyle{ m \ge n+4}\), to dostajemy sprzeczność, bo
\(\displaystyle{ m^3-n^3=(m-n)(m^2+mn+n^2)>(m-n) \cdot 3mn \ge 12mn=7mn+5mn \ge 7mn+5}\).

Zostało więc sprawdzić ręcznie przypadki \(\displaystyle{ m=n+3}\), \(\displaystyle{ m=n+2}\), \(\displaystyle{ m=n+1}\).

Wstawiając, upraszczając i rozwiązując równania kwadratowe, dostajemy dobre rozwiązanie jedynie w przypadku \(\displaystyle{ m=n+2}\), a mianowicie otrzymujemy wtedy \(\displaystyle{ n=1}\), co daje parę \(\displaystyle{ (m,n)=(3,1)}\).

Nowe zadanie:
Znajdź wszystkie trójki liczb całkowitych \(\displaystyle{ (x, y, z)}\) spełniające równanie
\(\displaystyle{ (x+y+z)^2=2(x^2+y^2+z^2)}\),
przy czym zachodzi warunek \(\displaystyle{ NWD(x, y, z)=1}\).
(Delta - Klub 44M - zadania III 2019 - Zadanie 778)

\(\displaystyle{ (x+y+z)^2=2\left[ \left( x+y+z\right)^2-2\left( xy+xz+yz\right) \right] }\)

\(\displaystyle{ x+y+z=u , xy+xz+yz=v}\)

\(\displaystyle{ u^2=2\left[ u^2-2v\right] }\)

\(\displaystyle{ u^2=4v , v=s^2}\)

\(\displaystyle{ u=2s , v=s^2}\)

\(\displaystyle{ x+y+z=s, xy+xz+yz=s^2}\)

\(\displaystyle{ z=2s-x-y}\)

\(\displaystyle{ xy+(x+y)(2s-x-y)=s^2}\)

\(\displaystyle{ xy=A, x+y=B}\)

\(\displaystyle{ A+B(2s-B)=s^2}\)

\(\displaystyle{ B^2-2sB+s^2-A=0}\)

\(\displaystyle{ \left( B-s\right)^2=A , A=a^2 }\)

\(\displaystyle{ B-s=a \vee B-s=-a}\)

\(\displaystyle{ B=s+a \vee B=s-a}\)

(1) \(\displaystyle{ x+y=s+a \wedge xy=a^2}\)

lub:

(2) \(\displaystyle{ x+y=s-a \wedge xy=a^2}\)


(1):
\(\displaystyle{ x^2-(s+a)x+a^2 }\)

\(\displaystyle{ \Delta=s^2-3a^2+2sa=t^2}\)

\(\displaystyle{ s^2+2as-3a^2-t^2=0}\)

\(\displaystyle{ \Delta_{1}=4a^2+12a^2+4t^2=r^2}\)

\(\displaystyle{ 16a^2+4t^2=r^2 , r=2p}\)

\(\displaystyle{ 4a^2+t^2=p^2}\)

\(\displaystyle{ (2a)^2+t^2=p^2}\)

\(\displaystyle{ 2a=k^2-l^2 , t=2kl , p=k+2+l^2 , r=2k^2+2l^2 , k,l=2i \vee k,l=2i+1}\)

\(\displaystyle{ s_{1}=- \frac{3k^2+l^2}{2} \vee s_{2}= \frac{k^2+3l^2}{2}}\)

\(\displaystyle{ x^2+(k^2+l^2)x+\left( \frac{k^2-l^2}{2} \right)^2=0 \vee x^2-(k^2+l^2)x+\left( \frac{k^2-l^2}{2} \right)^2=0 }\)

\(\displaystyle{ x_{1}=- \frac{k^2+l^2+2kl}{2} \vee x_{1}=- \frac{k^2+l^2-2kl}{2} }\)

(2):
\(\displaystyle{ x^2-(s-a)x+a^2=0}\)

Tu się sprowadza do sytuacji analogicznej:

\(\displaystyle{ x^2-(k^2+l^2)x+a^2=0 \vee x^2+(k^2+l^2)x+a^2=0}\)

Zatem rozwiązania będą:

\(\displaystyle{ x=- \frac{k^2+l^2+2kl}{2} , y=- \frac{k^2+l^2-2kl}{2} , z=-2k^2}\)

albo:

\(\displaystyle{ x= \frac{k^2+l^2+2kl}{2} , y= \frac{k^2+l^2-2kl}{2} , z=2l^2}\)

lub ich permutacje...

cnd...

oraz \(\displaystyle{ k , l }\) są tej samej parzystości...

Ale równanie \(\displaystyle{ x^2+y^2+z^2 = 2(xy+yz+zx)}\) można tez doprowadzić do \(\displaystyle{ (z-x-y)^2 = 4xy}\) tj. \(\displaystyle{ \sqrt{x} - \sqrt{y} = \sqrt{z} }\)
tj
\(\displaystyle{ \begin{cases} x = a^2 \\ y=b^2 \\ z=(a-b)^2 \end{cases}}\)

Ja tylko chciałem zauważyć, że w zadaniu było założenie o \(\displaystyle{ \NWD(x,y,z)=1}\), a rozwiązania arka nie spełniają tego założenia. Nie wczytywałem się, ponieważ brak tekstu mnie trochę odrzucił, natomiast może to być poprawny argument, że rozwiązań o takiej własności nie ma, ponieważ o ile rozwiązanie arka jest poprawne, to pokazuje ono, że jeśli rozwiązania istnieją, to są tej postaci, a więc przy założeniu odnośnie \(\displaystyle{ \NWD}\) nie istnieją. Obawiam się jednak, że tak nie jest, ponieważ wolfram wypluł mi na przykład \(\displaystyle{ x=-9, y=-4, z=-1}\) z permutacjami, a ono nie jest takiej postaci, jak uzyskane przez arka. Jak wrócę wieczorem, to może trochę pomyślę…

mol_ksiazkowy, z kolei Ty używasz symboli \(\displaystyle{ \sqrt{x}, \ \sqrt{y}, \ \sqrt{z}}\), a równanie jest w całkowitych. Natomiast zacząłem podobnie, później łatwo widać, że \(\displaystyle{ 4xy}\) musi być kwadratem, więc \(\displaystyle{ xy}\) też, ale niewiele więcej z tego, jak na razie, wycisnąłem.

Ja napisałem wyraźnie, że k,l musi być albo parzyste albo nieparzyste jednocześnie, bo mi to założenie wyglądało na dość sztuczne i w sumie niepotrzebne.

Możliwe, że tych rozwiązań względnie pierwszych jest skończenie wiele...

Premislav pisze: ↑1 gru 2019, o 16:43 Ja tylko chciałem zauważyć, że w zadaniu było założenie o \(\displaystyle{ \NWD(x,y,z)=1}\), a rozwiązania arka nie spełniają tego założenia. Nie wczytywałem się, ponieważ brak tekstu mnie trochę odrzucił, natomiast może to być poprawny argument, że rozwiązań o takiej własności nie ma, ponieważ o ile rozwiązanie arka jest poprawne, to pokazuje ono, że jeśli rozwiązania istnieją, to są tej postaci, a więc przy założeniu odnośnie \(\displaystyle{ \NWD}\) nie istnieją. Obawiam się jednak, że tak nie jest, ponieważ wolfram wypluł mi na przykład \(\displaystyle{ x=-9, y=-4, z=-1}\) z permutacjami, a ono nie jest takiej postaci, jak uzyskane przez arka. Jak wrócę wieczorem, to może trochę pomyślę…

mol_ksiazkowy, z kolei Ty używasz symboli \(\displaystyle{ \sqrt{x}, \ \sqrt{y}, \ \sqrt{z}}\), a równanie jest w całkowitych. Natomiast zacząłem podobnie, później łatwo widać, że \(\displaystyle{ 4xy}\) musi być kwadratem, więc \(\displaystyle{ xy}\) też, ale niewiele więcej z tego, jak na razie, wycisnąłem.

O ile się nie pomyliłem to gdy rozwiniemy wyjściowe równanie i rozważymy \(\displaystyle{ d= NWD(x,y)}\) to łatwo dostaniemy, że \(\displaystyle{ d=1}\) i wtedy usprawiedliwione jest założenie, że \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są kwadratami (lub liczbami przeciwnymi do kwadratu) liczby całkowitej, dalej chyba będzie tak jak u mola (przy czym musimy uważać na ujemne \(\displaystyle{ x}\) i \(\displaystyle{ y}\)).

Ciężko i grzeszno byłoby też odrzucić tak szeroką gamę rozwiązań, które znalazłem...

earl grey pisze: ↑1 gru 2019, o 17:33
O ile się nie pomyliłem to gdy rozwiniemy wyjściowe równanie i rozważymy \(\displaystyle{ d= NWD(x,y)}\) to łatwo dostaniemy, że \(\displaystyle{ d=1}\) i wtedy usprawiedliwione jest założenie, że \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są kwadratami (lub liczbami przeciwnymi do kwadratu) liczby całkowitej, dalej chyba będzie tak jak u mola (przy czym musimy uważać na ujemne \(\displaystyle{ x}\) i \(\displaystyle{ y}\)).

Masz rację, to w zasadzie absolutnie kluczowa obserwacja.
Ponadto jeśli \(\displaystyle{ x,y,z}\) są rozwiązaniami, to \(\displaystyle{ -x,-y, -z}\) też nimi są i oczywiście wśród trzech liczb znajdziemy dwie niedodatnie lub dwie nieujemne, więc możemy dla ustalenia uwagi założyć, że \(\displaystyle{ x\ge 0, \ y\ge 0}\) (i potem uzyskać pozostałe rozwiązania dzięki zmianie znaków lub cyklicznemu przesunięciu).
Wtedy równanie redukuje się do przypadków
\(\displaystyle{ z-x-y=2\sqrt{xy}, \ z-x-y=-2\sqrt{xy}}\), przy czym \(\displaystyle{ x,y}\) są kwadratami liczb całkowitych, a stąd też, po zauważeniu wzorów skróconego mnożenia, mamy \(\displaystyle{ z\ge 0}\) i zostajemy z rozwiązaniami \(\displaystyle{ x=a^{2}, \ y=b^{2}, \ z=(a-b)^{2}}\), gdzie \(\displaystyle{ a,b\in \NN^{+}, \ \NWD(a,b)=1}\) oraz permutacjami i odbiciami znaków, tj. również \(\displaystyle{ x=-a^{2}, \ y=-b^{2}, \ z=-(a-b)^{2}}\) etc.

Proponuję, by następne zadanie zadał \(\displaystyle{ x\in \left\{\textbf{earl grey}, \ \textbf{mol_ksiazkowy}\right\}}\).

Udowodnić, że jeśli \(\displaystyle{ k}\) jest dowolną liczbą naturalną, to istnieje liczba naturalna \(\displaystyle{ n}\) taka, że w przedziale \(\displaystyle{ (n, 2n)}\) jest co najmniej \(\displaystyle{ k}\) liczb pierwszych.

Wracając do poprzedniego ale ze mnie głąb , nie zauważyłem , że skoro:

\(\displaystyle{ (x,y,z) =d}\)

to:

\(\displaystyle{ \left( \frac{x}{d} , \frac{y}{d} , \frac{z}{d} \right)=1 }\)

Też jest rozwiązaniem równania, a wtedy będą względnie pierwsze już...

Dodano po 2 godzinach 19 minutach 50 sekundach:
W tym ostatnim skoro wiadomo, że:

\(\displaystyle{ \Pi(x)= \int_{2}^{x} \frac{dt}{\ln t} +\epsilon(x)}\)


\(\displaystyle{ \Pi(2x)= \int_{2}^{2x} \frac{dt}{\ln t} +\epsilon(2x)}\)

to wtedy:

\(\displaystyle{ \Pi(2x)-\Pi(x)=\int_{x}^{2x} \frac{dt}{\ln t} +coś}\)

Dobierając odpowiednio wielkie \(\displaystyle{ x}\) można upchać tam dowolną ilość liczb pierwszych...

Biorąc pod uwagę, że funkcja:

\(\displaystyle{ Li(x)}\) - jest ściśle i silnie rosnąca i dodatnia...

Może ten wątek ożyje. Zadanko:
Znajdź wszystkie takie naturalne dodatnie liczby \(\displaystyle{ n}\), dla których równocześnie obie liczby: \(\displaystyle{ n^n + 1}\) i \(\displaystyle{ (2n)^{2n} + 1}\) są pierwsze.

Dodano po 11 godzinach 26 minutach 56 sekundach:
Nowe zadanie:
niech \(\displaystyle{ x,y}\) będą liczbami całkowitymi dodatnimi niemającymi dzielników pierwszych większych niż \(\displaystyle{ 5}\). Proszę rozwiązać równanie \(\displaystyle{ x^{2}-y^{2}=2^{k} }\) dla całkowitych nieujemnych \(\displaystyle{ k}\).