Matematyka.pl

Zastanawia mnie jak pokazać następujący 'oczywisty' fakt, gdyż będzie można go potem zastosować do przejrzystego dowodu podstawowego twierdzenia arytmetyki. Jak zatem udowodnić fakt mówiący, że:
Jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli iloczyn \(\displaystyle{ n \cdot m}\) liczb naturalnych, to \(\displaystyle{ p}\) dzieli \(\displaystyle{ n}\) lub \(\displaystyle{ p}\) dzieli \(\displaystyle{ m;}\)
nie korzystając z podstawowego twierdzenia arytmetyki o jednoznaczności rozkładu liczby naturalnej na czynniki pierwsze
Możemy natomiast korzystać z faktu mówiącego, że każda liczba naturalna jest iloczynem jednej lub dwóch lub trzech lub ... skończenie wielu liczb pierwszych. Dzięki temu będę miał bardzo prosty i przejrzysty dowód podstawowego twierdzenia arytmetyki( patrz książkę 'Co to jest matematyka', R. Courant i H.Robbins, str.74 ).

Chciałem nadmienić, że p może dzielić jednocześnie i m i n

mówię o tym bo pewnie nie dla wszystkich jest to oczywiste...

Łap teoria-liczb-f26/male-twierdzenie-ferma ... l#p5166363

Dziękuję.
Ja udowodniłem to w inny, bardziej bezpośredni, sposób.
Podajmy najpierw pewien Lemat:
Lemat: Jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli iloczyn \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych, to \(\displaystyle{ p}\) jest równa pewnemu składnikowi tego iloczynu. Dowodzimy ten fakt indukcyjnie, ze względu na ilość składników tego iloczynu. Oto:
INDUKCYJNY DOWÓD TEGO FAKTU:
Jeśli \(\displaystyle{ n=1}\), i \(\displaystyle{ p|p_1}\), to ponieważ \(\displaystyle{ p_1}\) jest liczbą pierwszą (i \(\displaystyle{ p}\) również), więc ponieważ \(\displaystyle{ p \neq 1}\), to \(\displaystyle{ p=p_1}\), co dowodzi podstawy indukcji.
Jeśli \(\displaystyle{ n=2}\), i \(\displaystyle{ p |\left( p_1 \cdot p_2 \right)}\), to iloczyn \(\displaystyle{ \left( p_1 \cdot p_2\right)}\) ma dokładnie cztery dzielniki: \(\displaystyle{ 1, p_1, p_2}\) i \(\displaystyle{ \left( p_1 \cdot p_2\right).}\) Ponieważ \(\displaystyle{ p \neq 1}\), i \(\displaystyle{ \left( p_1 \cdot p_2\right)\not\in \mathbb{P}}\), tzn. nie jest to liczba pierwsza, a \(\displaystyle{ p}\) jest liczbą pierwszą, więc \(\displaystyle{ \left( p_1 \cdot p_2\right) \neq p}\), więc pozostają możliwości: \(\displaystyle{ p=p_1}\) lub \(\displaystyle{ p=p_2}\), czego należało dowieść.
Krok indukcyjny:
Załóżmy, że fakt zachodzi dla \(\displaystyle{ n}\), gdzie \(\displaystyle{ n \ge 2}\). Pokażemy, że ten fakt będzie zachodził dla \(\displaystyle{ \left( n+1\right)}\).
Niech \(\displaystyle{ p \in \mathbb{P}}\), i niech \(\displaystyle{ p_1, p_2, \ldots, p _{n+1}}\) będą liczbami pierwszymi. Jeśli \(\displaystyle{ p}\) dzieli \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p _{n+1}= \left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right) \cdot p _{n+1}}\), to ponieważ \(\displaystyle{ n \ge 2}\), i \(\displaystyle{ p \neq \left( p_1 \cdot p_2 \cdot \ldots \cdot p
_n\right)}\), bo \(\displaystyle{ \left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right)}\) nie jest liczbą pierwszą, a \(\displaystyle{ p}\) jest liczbą pierwszą, więc te liczby są różne, więc z przypadku \(\displaystyle{ n=2}\) wynika, że \(\displaystyle{ p=p _{n+1}}\), co dowodzi kroku indukcyjnego.
Zasada indukcji matematycznej dowodzi tego faktu.\(\displaystyle{ \square}\)

Coś dziwny jest ten dowód indukcyjny, bo nie korzysta on z założenia indukcyjnego. Ale myślę, że nie jest to konieczne, bo jeśli \(\displaystyle{ 2+2=4}\), to dla każdego \(\displaystyle{ n \in \NN}\): \(\displaystyle{ 2+2=4}\), i nie musimy używać tutaj, do dowodu tego faktu, założenia indukcyjnego.

Łatwo będzie teraz udowodnić nasz fakt:
Jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli iloczyn \(\displaystyle{ \left( n \cdot m\right)}\) liczb naturalnych, to \(\displaystyle{ p}\) dzieli \(\displaystyle{ n}\) lub \(\displaystyle{ p}\) dzieli \(\displaystyle{ m}\). Oto:
PROSTY DOWÓD TEGO FAKTU:
Ponieważ każda liczba naturalna jest iloczynem jednej lub dwóch lub trzech lub... skończenie wielu liczb pierwszych, więc \(\displaystyle{ n= n_1 \cdot n_2 \cdot \ldots \cdot n_k}\), gdzie liczby naturalne \(\displaystyle{ n_i}\) są pierwsze, i \(\displaystyle{ m= m_1 \cdot m_2 \cdot \ldots \cdot m _{l}}\), gdzie liczby \(\displaystyle{ m_i}\) są pierwsze. Na mocy łączności mnożenia liczb naturalnych:
\(\displaystyle{ p| \left[ \left( n \cdot m\right)= \left( n_1 \cdot n_2 \cdot \ldots \cdot n_k\right) \cdot \left( m_1 \cdot m_2 \cdot \ldots \cdot m_l\right) \right];}\)
więc na mocy Lematu powyżej: \(\displaystyle{ p=n_i}\), dla pewnego \(\displaystyle{ i=1,2,\ldots,k;}\) lub \(\displaystyle{ p=m_j,}\) dla pewnego \(\displaystyle{ j}\).
Jeśli \(\displaystyle{ p=n_i}\), to \(\displaystyle{ p|n}\), a jeśli \(\displaystyle{ p=m_j}\), to \(\displaystyle{ p|m.\square}\)

Łatwo można przez prostą indukcję uogólnić ten fakt, tzn.:
Jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli iloczyn \(\displaystyle{ \left( x_1 \cdot x_2 \cdot \ldots \cdot x_n\right)}\) liczb naturalnych, to \(\displaystyle{ p}\) dzieli \(\displaystyle{ x_i}\), dla pewnego \(\displaystyle{ i=1,2,\ldots,n}\).
Można to łatwo indukcyjnie udowodnić.

W takim razie jesteśmy gotowi aby udowodnić podstawowe twierdzenie matematyki o jednoznaczności rozkładu liczby naturalnej na czynniki pierwsze.

Niech \(\displaystyle{ X \in \NN}\), i niech \(\displaystyle{ X= n_1 \cdot n_2 \cdot \ldots \cdot n_r=m_1 \cdot m_2 \cdot \ldots \cdot m_S}\), gdzie \(\displaystyle{ n_i \in \PP,}\) i gdzie \(\displaystyle{ m _{j} \in \PP.}\)
Ponieważ \(\displaystyle{ n_1}\) dzieli lewą stronę tej równości, więc \(\displaystyle{ n_1}\) dzieli również prawą stronę, i ponieważ \(\displaystyle{ n_1}\) jest liczbą pierwszą, więc na mocy powyższego faktu: \(\displaystyle{ n_1}\) dzieli \(\displaystyle{ m_j}\), dla pewnego \(\displaystyle{ j}\). Ponieważ liczba \(\displaystyle{ m_j}\), na mocy założenia, jest liczbą pierwszą, i \(\displaystyle{ n_1}\) również, więc \(\displaystyle{ n_1 \neq 1}\), i \(\displaystyle{ n_1=m_j.}\) Skreślamy teraz te czynniki, i rozważmy liczbę:
\(\displaystyle{ X_2:= n_2 \cdot n_3 \cdot \ldots \cdot n_r= m_1 \cdot m_2 \cdot \ldots m _{j-1} \cdot m _{j+1} \cdot m _{j+2} \cdot \ldots m_S.}\)
Wtedy \(\displaystyle{ n_2}\) dzieli lewą stronę tej równości, zatem \(\displaystyle{ n_2}\) dzieli również prawą stronę, a więc, na mocy powyższego faktu: \(\displaystyle{ n_2| m_i}\), dla \(\displaystyle{ i \neq j}\); i ponieważ \(\displaystyle{ n_2}\) i \(\displaystyle{ m_i}\) są liczbami pierwszymi, to \(\displaystyle{ n_2=m_i,}\), gdzie \(\displaystyle{ i \neq j}\). Skreślamy zatem te dwa czynniki, i postępując dalej w ten sposób, otrzymamy, że lewa strona tej równości będzie równa \(\displaystyle{ 1}\), a prawa strona też również będzie równa \(\displaystyle{ 1}\) (każdy czynnik \(\displaystyle{ m_k}\) jest liczbą pierwszą, a więc jest równy co najmniej dwa, więc muszą być wszystkie te czynniki skreślone, aby zachodziła równość). A zatem do każdej liczby \(\displaystyle{ n_k}\) można dobrać jednoznacznie liczbę \(\displaystyle{ m _{i_k}}\), gdzie numery \(\displaystyle{ i_k}\) są coraz to nowe. A zatem rozkłady liczby \(\displaystyle{ X}\) są (poza kolejnością czynników) są takie same.\(\displaystyle{ \square}\)

Na koniec dodam takie moje odkrycie, że prawo łączności mnożenia liczb naturalnych \(\displaystyle{ \left( a \cdot b\right) \cdot c= a \cdot \left( b \cdot c\right)}\) można zilustrować przy pomocy kostki prostopadłościennej podzielonej na kostki jednostkowe:
Rozważmy kostkę o wymiarach \(\displaystyle{ a \times b \times c}\), gdzie \(\displaystyle{ a,b,c \ge 1}\), podzieloną na \(\displaystyle{ \left( a \cdot b \cdot c\right)}\) kostek jednostkowych. Widać więc, że odpowiada to (dokładniej) liczbie \(\displaystyle{ \left( a \cdot b\right) \cdot c}\), jeśli będziemy liczyć najpierw kostki leżące na płaszczyźnie \(\displaystyle{ XY}\), i potem będziemy liczyć kostki na równoległych płaszczyznach leżących powyżej. Teraz ścianę tej kostki o wymiarach \(\displaystyle{ b \times c}\) (z prawej strony) połóżmy dnem do podłoża obracając jednocześnie całą bryłę o \(\displaystyle{ 90 ^{\circ}}\). Wszystkich kostek jednostkowych będzie oczywiście tyle samo, ale cała bryła będzie wtedy kostką o wymiarach \(\displaystyle{ \left( b \times c\right) \times a}\), i ponieważ mnożenie jest przemienne, więc \(\displaystyle{ \left( b \cdot c\right) \cdot a= a \cdot \left( b \cdot c\right)=\left( a \cdot b\right) \cdot c}\).

Niech \(\displaystyle{ p \in \mathbb{P}}\), i niech \(\displaystyle{ p_1, p_2, \ldots, p _{n+1}}\) będą liczbami pierwszymi. Jeśli \(\displaystyle{ p}\) dzieli \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p _{n+1}= \left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right) \cdot p _{n+1}}\), to ponieważ \(\displaystyle{ n \ge 2}\), i \(\displaystyle{ p \neq \left( p_1 \cdot p_2 \cdot \ldots \cdot p
_n\right)}\), bo \(\displaystyle{ \left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right)}\) nie jest liczbą pierwszą, a \(\displaystyle{ p}\) jest liczbą pierwszą, więc te liczby są różne, więc z przypadku \(\displaystyle{ n=2}\) wynika, że \(\displaystyle{ p=p _{n+1}}\), co dowodzi kroku indukcyjnego.

Czy można się odwołać do przypadku 2): \(\displaystyle{ p_1...p_n}\) nie jest liczbą pierwszą....

mol_ksiazkowy pisze: ↑4 mar 2024, o 20:17 Czy można się odwołać do przypadku 2): \(\displaystyle{ p_1...p_n}\) nie jest liczbą pierwszą....

Nie można, trzeba skorzystać z założenia indukcyjnego, które JG uznał za zbędne...

JK

trzeba skorzystać z założenia indukcyjnego, które JG uznał za zbędne...

Już mnie nic tak nie zaskoczy jak dowód twierdzenia, którego założenie jest zbędne, szczerze to mi się podoba...
(Myślę, że uda mi się udowodnić kilka twierdzeń bez żadnych założeń)...

Zauważcie, że sprawdziłem warunek oddzielnie dla \(\displaystyle{ n=1}\) i dla \(\displaystyle{ n=2}\). A stąd indukcję można kontynuować od \(\displaystyle{ n=2}\). A wtedy iloczyn \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p_n}\), jako iloczyn co najmniej dwóch liczb pierwszych, nie jest liczbą pierwszą, bo oprócz \(\displaystyle{ 1}\) i samej siebie dzieli go np. \(\displaystyle{ p_1}\).

ale \(\displaystyle{ \left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right) \cdot p _{n+1} = p_1 \cdot (p_2 \cdot .... \cdot p_{n+1})}\) więc \(\displaystyle{ p = p_1}\)...

Jakub Gurak pisze: ↑4 mar 2024, o 22:00 Zauważcie, że sprawdziłem warunek oddzielnie dla \(\displaystyle{ n=1}\) i dla \(\displaystyle{ n=2}\). A stąd indukcję można kontynuować od \(\displaystyle{ n=2}\).

W kroku indukcyjnym piszesz

Jakub Gurak pisze: ↑4 mar 2024, o 18:06więc z przypadku \(\displaystyle{ n=2}\) wynika, że \(\displaystyle{ p=p _{n+1}}\), co dowodzi kroku indukcyjnego.

więc korzystasz z przeprowadzonego wcześniej dowodu dla \(\displaystyle{ n=2}\). Problem polega na tym, że korzystasz z niego w warunkach, które nie odpowiadają sytuacji dla \(\displaystyle{ n=2}\) (tam jest iloczyn dwóch liczb pierwszych, a tutaj nie), więc nie wolno Ci tego zrobić. Dowód jest niepoprawny.

JK

Przepraszam, weszłem na niebezpieczne tory...
Zastanowie się jak to poprawić.

Dodano po 2 dniach 29 minutach 16 sekundach:
Ale jest to fakt oczywisty, bo on mówi, że jedynymi dzielnikami pierwszymi iloczynu \(\displaystyle{ x=p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych są jego czynniki \(\displaystyle{ p_1,p_2, \ldots, p_n}\). Jasne jest, że inne dzielniki, to albo \(\displaystyle{ 1}\), która to liczba nie jest liczbą pierwszą, albo mogą być dzielniki złożone- nawet ja myśląc wczoraj nad dowodem tego oczywistego faktu to straciłem zapał, ale wpadłem jednak jeszcze na pomysł aby wykorzystać wzór na wszystkie dzielniki danej liczby naturalnej i poprawiłem ten dowód.
Przypomnijmy (zobacz książkę 'Co to jest matematyka' Ćwiczenie na str. 47), że jeśli liczbę naturalną \(\displaystyle{ a}\) przedstawimy w postaci:

\(\displaystyle{ a= p_1 ^{ \alpha _{1} } \cdot p_2 ^{ \alpha _{2} } \cdot \ldots \cdot p _{n} ^{ \alpha _{n} };}\)

gdzie \(\displaystyle{ p_i}\) są to różne liczby pierwsze, czyli \(\displaystyle{ p_i \neq p_j}\), dla \(\displaystyle{ i \neq j}\); a \(\displaystyle{ \alpha _{i} \in \NN_+}\), to zbiorem wszystkich dzielników liczby \(\displaystyle{ a}\), jest zbiór:

\(\displaystyle{ \left\{ p_1 ^{ \beta _{1} } \cdot p_2 ^{ \beta _{2} } \cdot \ldots \cdot p _{n} ^{ \beta _{n} } \Bigl| \ \ \beta _{i} \in \NN, 0 \le \beta _{i} \le \alpha _{i} \right\}.}\)

Stąd łatwo wynika (choć może w sposób trochę żmudny), że dzielnikami iloczynu \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych (niekoniecznie różnych) są tylko liczby postaci:

\(\displaystyle{ s= p_1 ^{ \alpha _{1} } \cdot p_2 ^{ \alpha _{2} } \cdot \ldots \cdot p _{n} ^{ \alpha _{n} }, \hbox{ gdzie } \alpha _{i} \in \left\{ 0,1\right\}.}\)

Przypuśćmy teraz nie wprost, że ten iloczyn \(\displaystyle{ p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych ma dzielnik pierwszy różny od liczb \(\displaystyle{ p_1, p_2,\ldots, p_n}\). Wtedy możliwe są trzy przypadki:

1): \(\displaystyle{ \alpha _{1}= \alpha _{2}= \ldots = \alpha _{n}=0}\).
2): Dla pewnego \(\displaystyle{ i}\): \(\displaystyle{ \alpha _{i}= 1}\), i \(\displaystyle{ \alpha _{j}= 0}\), dla \(\displaystyle{ j \neq i}\).
3): Dla pewnego \(\displaystyle{ i}\): \(\displaystyle{ \alpha _{i}=1}\), i dla pewnego \(\displaystyle{ j \neq i}\): \(\displaystyle{ \alpha _{j}=1}\).

1):Wtedy \(\displaystyle{ s=1}\), a \(\displaystyle{ 1 \notin \PP,}\) a \(\displaystyle{ s \in \PP}\)- sprzeczność.
2):Ten przypadek jest niemożliwy, bo wtedy \(\displaystyle{ s=p_i}\), a \(\displaystyle{ s \neq p_1, p_2, \ldots, p_n}\).
3): Wtedy \(\displaystyle{ p_i|s}\) i \(\displaystyle{ p_i \neq 1,}\) bo \(\displaystyle{ 1}\) nie jest liczbą pierwszą, i \(\displaystyle{ p_i \neq s}\), bo \(\displaystyle{ s \ge p_i \cdot p_j \ge 2p_i}\), a zatem \(\displaystyle{ s}\) nie jest liczbą pierwszą- sprzeczność.
Wobec czego jedynymi dzielnikami pierwszymi iloczynu \(\displaystyle{ x=p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych są te czynniki tego iloczynu.\(\displaystyle{ \square}\)
Jakby ktoś zastanawiał się czy nie ma błędu w dalszych dowodach tego postu to- to sprawdziłem, i to dwa razy, również wczoraj sprawdziłem po zrobieniu tej poprawki i- i wszystko jest dobrze.

Na koniec chciałbym podzielić się z Wami takim spostrzeżeniem, że można mówić o ciągu \(\displaystyle{ f:\NN \rightarrow \PP}\) wszystkich liczb pierwszych, przynajmniej teoretycznie:
Przypuśćmy, że znaleźliśmy (poczynając od \(\displaystyle{ p_1=2}\)) przypuśćmy, że znaleźliśmy \(\displaystyle{ n}\) początkowych liczb pierwszych \(\displaystyle{ p_1, p_2, \ldots, p_n.}\) Rozważmy liczbę \(\displaystyle{ X:=\left( p_1 \cdot p_2 \cdot \ldots \cdot p_n\right) +1}\). Jeśli jest to liczba pierwsza, to jest to nowa liczba pierwsza, a jeśli nie jest to liczba pierwsza, to \(\displaystyle{ X}\) ma dzielnik pierwszy różny od liczb \(\displaystyle{ p_1, p_2, \ldots, p_n}\) (bo daje resztę \(\displaystyle{ 1}\) przy dzieleniu przez każdą z nich). Ponieważ każdy dzielnik liczby naturalnej dodatniej jest od niej mniejszy lub równy, to możemy ten dzielnik pierwszy wyznaczyć przez kolejne próbowanie \(\displaystyle{ p=2, p=3, \ldots, p=X}\). A zatem mamy kolejną liczbę pierwszą. Postępując dalej w ten sposób otrzymamy ciąg \(\displaystyle{ f:\NN \rightarrow \PP}\) wszystkich liczb pierwszych\(\displaystyle{ .\square}\)

Wobec czego jedynymi dzielnikami pierwszymi iloczynu \(\displaystyle{ x=p_1 \cdot p_2 \cdot \ldots \cdot p_n}\) liczb pierwszych są te czynniki tego iloczynu.\(\displaystyle{ \square}\)

To trochę jest "masło-maślane"...

Jakub Gurak pisze: ↑7 mar 2024, o 16:27 Postępując dalej w ten sposób otrzymamy ciąg \(\displaystyle{ f:\NN \rightarrow \PP}\) wszystkich liczb pierwszych\(\displaystyle{ .\square}\)

Nie widzę, dlaczego \(\displaystyle{ f}\) miałaby być surjekcją.

Ja bym to uzasadnił tak, że jeśli \(\displaystyle{ p\in\PP}\) jest liczbą pierwszą, to:
\(\displaystyle{ p \in \stackrel { \rightarrow }{f} \left( p=\left\{ n \in \NN: \ n<p\right\} \right) \subset \stackrel { \rightarrow }{f}\left( \NN\right)= f _{P};}\)
który to pierwszy z tych trzech faktów można łatwo indukcyjnie udowodnić, a pozostałe przejścia są oczywiste.\(\displaystyle{ \square}\)

A zastanowiłeś się czego potrzebujesz żeby się przekonać o pierwszosci liczby `p_n`?