Dowód faktoryzacji

[PieknoMatematyki]

Czy mógłby ktoś sprawdzić czy ten dowód jest poprawny? (i czy w ogóle jest dowodem)


Potrzebuję trzech faktów:
1. Jest nieskończenie wiele liczb pierwszych (ze względu na Wasz czas - pominę dowód).

2. Jest nieskończenie wiele liczb złożonych.
To jasno wynika z faktu nieskończoności liczb pierwszych.

3. Każdą liczbę naturalną większą od jeden można przedstawić za pomocą iloczynu liczb pierwszych.
Dowód:
Załóżmy nie wprost, że istnieją liczby naturalne, które nie są ani pierwsze, ani złożone, zatem takie, których nie da się przedstawić za pomocą iloczynu liczb pierwszych.
Stąd istnieje najmniejsza taka liczba naturalna (z ograniczenia dolnego liczb naturalnych).
Ma ona minimum dwa dzielniki (samą siebie i jeden, co wynika bezpośrednio z aksjomatu: \(\displaystyle{ 1 \cdot n = n}\)), ale nie może mieć dokładnie dwóch dzielników (bo wówczas jest pierwsza). Zatem ma minimum trzy dzielniki (\(\displaystyle{ 1}\), samą siebie, \(\displaystyle{ x}\)), gdzie \(\displaystyle{ x}\) jest naturalna, ale nie może być pierwsza, ani złożona (bo wówczas nasza liczba miała by rozkładzie czynniki pierwsze).
Zauważmy, ze \(\displaystyle{ x}\) jest mniejsze od naszej liczby, co jest sprzeczne z założeniem o jej minimalności. Co było do wykazania.

Dowód jednoznaczności:
Załóżmy nie wprost, że istnieje liczba naturalna, która ma dwa różne rozkłady na czynniki pierwsze.

Wówczas istnieje najmniejsza taka liczba (z ograniczenia zbioru liczb naturalnych). Oznaczmy ją jako \(\displaystyle{ n}\).

\(\displaystyle{ n = p_1 p_2 \cdot \dots \cdot p_k = q_1 q_2 \cdot \dots \cdot q_t}\) (gdzie \(\displaystyle{ k,t}\) naturalne)

Fakt 1: Z minimalności \(\displaystyle{ n}\) wiemy, że żadna liczba z \(\displaystyle{ p_1 p_2 \cdot \dots \cdot p_k}\) nie powtarza się w \(\displaystyle{ q_1 q_2 \cdot \dots \cdot q_t}\) (bo wówczas moglibyśmy jest skrócić).

Liczba \(\displaystyle{ p_1}\) oczywiście dzieli \(\displaystyle{ n}\). W takim razie \(\displaystyle{ p_1}\) dzieli również \(\displaystyle{ q_1 q_2 \cdot \dots \cdot q_t}\) co jest sprzeczne z Faktem 1.

[matmatmm]

Zacznijmy może od tego, żeby precyzyjnie zdefiniować liczby pierwsze i złożone. Widzę, że nigdzie tego nie zrobiłeś, a w takich dowodach może to mieć znaczenie.

Liczbę \(\displaystyle{ p}\) nazywamy liczbą pierwszą, gdy jest liczbą naturalną, która ma dokładnie \(\displaystyle{ 2}\) dzielniki naturalne.

Ponieważ \(\displaystyle{ 1\cdot n=n}\) dla każdego \(\displaystyle{ n\in\NN}\), liczba \(\displaystyle{ p}\) jest pierwsza wtedy i tylko wtedy, gdy jest liczbą naturalną większą od \(\displaystyle{ 1}\), której jedynymi dzielnikami naturalnymi są \(\displaystyle{ 1}\) i \(\displaystyle{ p}\).

Sensowną definicją liczby złożonej jest:

Liczbę \(\displaystyle{ k}\) nazywamy liczbą złożoną, gdy \(\displaystyle{ k}\) jest liczbą naturalną większą od \(\displaystyle{ 1}\) i nie jest liczbą pierwszą.

Na podstawie tego co pisałem wcześniej, można napisać, że \(\displaystyle{ k}\) jest liczbą złożoną wtedy i tylko wtedy, gdy \(\displaystyle{ k}\) jest liczbą naturalną większą od \(\displaystyle{ 1}\), która ma dzielnik naturalny różny od \(\displaystyle{ 1}\) i \(\displaystyle{ k}\).

Można to jeszcze wzmocnić do: \(\displaystyle{ k}\) jest liczbą złożoną wtedy i tylko wtedy, gdy \(\displaystyle{ k}\) jest liczbą naturalną, która ma dzielnik \(\displaystyle{ m}\) taki, że \(\displaystyle{ 1<m<k}\)

Przechodząc do twojego rozumowania

2. Jest nieskończenie wiele liczb złożonych.
To jasno wynika z faktu nieskończoności liczb pierwszych.

Według mnie nie wynika to z tego jakoś bezpośrednio. Możesz rozwinąć?

3. Każdą liczbę naturalną większą od jeden można przedstawić za pomocą iloczynu liczb pierwszych.
Dowód:
Załóżmy nie wprost, że istnieją liczby naturalne, które nie są ani pierwsze, ani złożone, zatem takie, których nie da się przedstawić za pomocą iloczynu liczb pierwszych.

Na podstawie tego, co pisałem wcześniej, liczba naturalna, która nie jest ani pierwsza, ani złożona, to nieuchronnie liczba \(\displaystyle{ 1}\). Założenie nie wprost jest zatem nieadekwatne do tezy twierdzenia. Jeśli założysz dodatkowo, że ta liczba jest większa od \(\displaystyle{ 1}\), to owszem dojdziesz do sprzeczności, ale z tego nie wyniknie teza twierdzenia.

Inaczej mówiąc: Każda liczba naturalna większa od \(\displaystyle{ 1}\) jest pierwsza lub złożona, ale stąd jeszcze nie wynika, że jest iloczynem liczb pierwszych.

Stąd istnieje najmniejsza taka liczba naturalna (z ograniczenia dolnego liczb naturalnych).
Ma ona minimum dwa dzielniki (samą siebie i jeden, co wynika bezpośrednio z aksjomatu: \(\displaystyle{ 1 \cdot n = n}\)),

Tu jest błąd, bo tą najmniejszą liczbą naturalną jest \(\displaystyle{ 1}\) i nie ma ona minimum dwóch dzielników.

[PieknoMatematyki]

Według mnie nie wynika to z tego jakoś bezpośrednio. Możesz rozwinąć?

Liczby złożone (wynika to z Twojej definicji) to takie, które mają więcej niż dwa dzielniki. Iloczyn liczb pierwszych jest więc liczbą złożoną. Skoro jest nieskończenie wiele liczb pierwszych, to możemy stworzyć nieskończenie wiele ich różnych iloczynów. Więc liczb złożonych jest nieskończenie wiele.

Na podstawie tego, co pisałem wcześniej, liczba naturalna, która nie jest ani pierwsza, ani złożona, to nieuchronnie liczba \(\displaystyle{ 1}\). Założenie nie wprost jest zatem nieadekwatne do tezy twierdzenia. Jeśli założysz dodatkowo, że ta liczba jest większa od \(\displaystyle{ 1}\), to owszem dojdziesz do sprzeczności, ale z tego nie wyniknie teza twierdzenia.

Nie wiem czy tak nieuchronnie, mi brakuje tutaj uzasadnienia tego, że każda liczba złożona rozkłada się na czynniki pierwsze.
I myślę, że w tej sytuacji lepiej byłoby zamienić tezę trzy własnie na taką:
3. Każda liczba złożona rozkłada się na czynniki pierwsze.
Załóżmy nie wprost, że istnieje liczba złożona, która nie rozkłada się na czynniki pierwsze.
Musi istnieć najmniejsza taka liczba (no bo musi, najmniejsza liczba złożona to \(\displaystyle{ 4}\), niżej nie zejdziemy). Oznaczmy ją jako \(\displaystyle{ n}\).
\(\displaystyle{ n}\) posiada minimum trzy dzielniki (\(\displaystyle{ 1, n, x}\)). Zatem \(\displaystyle{ x}\) nie może mieć w rozkładzie liczby pierwszej. Zatem \(\displaystyle{ x}\) jest liczbą złożoną, która nie ma w rozkładzie czynników pierwszych, co jest sprzeczne z założeniem o minimalności \(\displaystyle{ n}\).

Tu jest błąd, bo tą najmniejszą liczbą naturalną jest 1 i nie ma ona minimum dwóch dzielników.

Prawda, tutaj powinno być założenie, że liczba naturalna jest większa od \(\displaystyle{ 1}\). To założenie rozwiązuje już problem.

[matmatmm]

Na podstawie tego, co pisałem wcześniej, liczba naturalna, która nie jest ani pierwsza, ani złożona, to nieuchronnie liczba \(\displaystyle{ 1}\). Założenie nie wprost jest zatem nieadekwatne do tezy twierdzenia. Jeśli założysz dodatkowo, że ta liczba jest większa od \(\displaystyle{ 1}\), to owszem dojdziesz do sprzeczności, ale z tego nie wyniknie teza twierdzenia.

Nie wiem czy tak nieuchronnie, mi brakuje tutaj uzasadnienia tego, że każda liczba złożona rozkłada się na czynniki pierwsze.

Wcale nie jest to konieczne. Wprost z definicji podanych przeze mnie wcześniej wynika, że każda liczba naturalna większa od \(\displaystyle{ 1}\) jest pierwsza lub złożona.

I myślę, że w tej sytuacji lepiej byłoby zamienić tezę trzy własnie na taką:
3. Każda liczba złożona rozkłada się na czynniki pierwsze.
Załóżmy nie wprost, że istnieje liczba złożona, która nie rozkłada się na czynniki pierwsze.
Musi istnieć najmniejsza taka liczba (no bo musi, najmniejsza liczba złożona to \(\displaystyle{ 4}\), niżej nie zejdziemy).

Czemu akurat \(\displaystyle{ 4}\)? Jesteśmy w dowodzie nie wprost, taka liczba tak naprawdę nie istnieje.

Oznaczmy ją jako \(\displaystyle{ n}\).
\(\displaystyle{ n}\) posiada minimum trzy dzielniki (\(\displaystyle{ 1, n, x}\)).

Do tego momentu jest OK.

Zatem \(\displaystyle{ x}\) nie może mieć w rozkładzie liczby pierwszej.

Czyli twierdzisz w tym miejscu, że \(\displaystyle{ x}\) nie jest podzielny przez żadną liczbę pierwszą? Dlaczego?

[PieknoMatematyki]

Wcale nie jest to konieczne. Wprost z definicji podanych przeze mnie wcześniej wynika, że każda liczba naturalna większa od 1 jest pierwsza lub złożona.

Ale z Twojej definicji nie wynika, że złożona jest MUSI mieć w rozkładzie liczby pierwsze.

Czemu akurat \(\displaystyle{ 4}\)? Jesteśmy w dowodzie nie wprost, taka liczba tak naprawdę nie istnieje.

To własnie wykazuję. Jeżeli istnieje, to z pewnością nie jest mniejsza od \(\displaystyle{ 4}\), bo to mogę sobie sprawdzić ręcznie. Czemu akurat \(\displaystyle{ 4}\)? Potrzebuję ograniczenia dolnego, a \(\displaystyle{ 4}\) jest najbliżej

Czyli twierdzisz w tym miejscu, że \(\displaystyle{ x}\) nie jest podzielny przez żadną liczbę pierwszą? Dlaczego?

Z założenia:

Załóżmy nie wprost, że istnieje liczba złożona, która nie rozkłada się na czynniki pierwsze.

Jeżeli jakakolwiek liczba pierwsza dzieli \(\displaystyle{ x}\), to mamy sprzeczność z założeniem (co nas raczej cieszy).

[matmatmm]

Ale z Twojej definicji nie wynika, że złożona jest MUSI mieć w rozkładzie liczby pierwsze.

Oczywiście, że nie. To właśnie chcesz udowodnić.

Czemu akurat \(\displaystyle{ 4}\)? Jesteśmy w dowodzie nie wprost, taka liczba tak naprawdę nie istnieje.

To własnie wykazuję. Jeżeli istnieje, to z pewnością nie jest mniejsza od \(\displaystyle{ 4}\), bo to mogę sobie sprawdzić ręcznie. Czemu akurat \(\displaystyle{ 4}\)? Potrzebuję ograniczenia dolnego, a \(\displaystyle{ 4}\) jest najbliżej

Każdy niepusty podzbiór zbioru liczb naturalnych ma element najmniejszy. Jest to więc krok zbędny.

Z założenia:

Załóżmy nie wprost, że istnieje liczba złożona, która nie rozkłada się na czynniki pierwsze.

Jeżeli jakakolwiek liczba pierwsza dzieli \(\displaystyle{ x}\), to mamy sprzeczność z założeniem (co nas raczej cieszy).

Gdzie tu jest ta sprzeczność?-- 22 sty 2019, o 23:17 --Okej. Chyba już rozumiem. Ty dowodzisz twierdzenie, że każda liczba naturalna ma dzielnik pierwszy. Liczba ma dzielnik pierwszy nie znaczy to samo, co liczba rozkłada się na czynniki pierwsze.

[PieknoMatematyki]

Gdzie tu jest ta sprzeczność?

liczba \(\displaystyle{ n}\) jest liczbą złożoną, która nie ma dzielnika pierwszego (z założenia nie wprost). Dlatego \(\displaystyle{ x}\) nie może być liczbą pierwszą, ani taką liczbą złożoną, która ma dzielniki pierwsze, bo inaczej ta liczba pierwsza, która jest dzielnikiem \(\displaystyle{ x}\) jest też dzielnikiem \(\displaystyle{ n}\).
Co przeczy założeniu, więc nie może tak być. Jedyna opcja to taka, że \(\displaystyle{ x}\) jest liczbą złożoną, która nie ma dzielników pierwszych. A \(\displaystyle{ x}\) musi być mniejsze od \(\displaystyle{ n}\), a to jest sprzeczne z założeniem minimalności \(\displaystyle{ n}\), czyli nie istnieje taki \(\displaystyle{ x}\), w takim razie \(\displaystyle{ n}\) jest pierwsza i wchodzimy w absurd.

EDIT: Dalej już prosto wykazać, że każda liczba naturalna ma rozkład na czynniki pierwsze.
1. Jeżeli liczba jest pierwsza - to oczywiste.
2. Jeżeli liczba jest złożona, to musi mieć dzielniki, które są pierwsze lub złożone (które w rozkładzie mają pierwsze), co wynika z dowodu powyżej. A skoro ma tylko takie dzielniki, to da się też taką liczbę przedstawić za pomocą iloczynu liczb pierwszych.

Właściwie to wystarczy, że każda liczba złożona będzie miała przynajmniej jeden dzielnik pierwszy.

[Jan Kraszewski]

2. Jeżeli liczba jest złożona, to musi mieć dzielniki, które są pierwsze lub złożone (które w rozkładzie mają pierwsze), co wynika z dowodu powyżej. A skoro ma tylko takie dzielniki, to da się też taką liczbę przedstawić za pomocą iloczynu liczb pierwszych.

No to nie jest dowód, tylko machanie rękami.

JK

[a4karo]

A poza tym, jak prosimy o ocenę dowodu to najpierw trzeba sformułować twierdzenie.

[PieknoMatematyki]

Uwzględniając wszystkie uwagi do tej pory:

Definicje:
Liczby pierwsze, to takie liczby naturalne większe od \(\displaystyle{ 1}\), które mają dokładnie dwa dzielniki naturalne.

Liczby złożone, to takie liczby naturalne większe od \(\displaystyle{ 1}\), które nie są pierwsze.

Liczba \(\displaystyle{ x}\) jest dzielnikiem liczby \(\displaystyle{ n}\) wtedy i tylko wtedy, gdy istnieje taka liczba naturalna \(\displaystyle{ k}\), że \(\displaystyle{ x \cdot k = n}\).

Teza: Wszystkie liczby złożone można przedstawić za pomocą iloczynu liczb pierwszych w sposób jednoznaczny (z dokładnością do kolejności czynników).

Dowód tezy:
W tym dowodzie skorzystam z następujących faktów:

1. Liczb pierwszych jest nieskończenie wiele.

2. Każda liczba naturalna z wyjątkiem jedynki ma przynajmniej dwa dzielniki naturalne.

Dowód:
Z aksjomatu:
\(\displaystyle{ \forall_{n\in \NN} \; n \cdot 1 = n}\)

każda liczba naturalna ma przynajmniej dwa dzielniki i są nimi: \(\displaystyle{ n}\) i \(\displaystyle{ 1}\), z wyjątkiem sytuacji, gdy \(\displaystyle{ n = 1}\).
To wynika wprost z definicji dzielnika, ponieważ \(\displaystyle{ 1,n \in \NN}\).

Wniosek: Zatem każda liczba złożona ma przynajmniej trzy dzielniki (bo jest naturalna i nie jest pierwsza).

3. Każda liczba naturalna większa od \(\displaystyle{ 1}\) ma przynajmniej jeden dzielnik pierwszy.

Dowód:
Dla liczby pierwszej dowód jasno wynika z faktu 2.

Załóżmy nie wprost, że istnieje liczba złożona, która nie ma dzielnika pierwszego.
Istnieje zatem najmniejsza taka liczba.
Zatem z wniosku do faktu 2. wynika, że liczba ta ma przynajmniej \(\displaystyle{ 3}\) dzielniki (\(\displaystyle{ 1,n,x}\)), \(\displaystyle{ x}\) z założenia nie wprost nie jest pierwsze. Zatem \(\displaystyle{ x}\) musi być złożone, a to przeczy założeniu minimalności \(\displaystyle{ n}\), co kończy dowód.

Teraz dowiodę, że każą liczbę złożoną można przedstawić za pomocą iloczynu liczb pierwszych.

Załóżmy nie wprost, że istnieje taka liczba złożona, której nie można przedstawić za pomocą iloczynu liczb pierwszych.

W takim razie istnieje najmniejsza taka liczba, oznaczmy ją jako \(\displaystyle{ k}\).
Zatem z faktu 3. wynika, że \(\displaystyle{ k = x \cdot n}\), gdzie \(\displaystyle{ x}\) jest liczbą pierwszą, a liczba \(\displaystyle{ n}\) jest naturalna różna od \(\displaystyle{ 1}\) (bo inaczej \(\displaystyle{ k}\) jest pierwsza).
Z założenia nie wprost wynika, że \(\displaystyle{ n}\) nie jest pierwsze, zatem musi być złożone, co przeczy założeniu o minimalności \(\displaystyle{ k}\), co kończy dowód.

Pozostało więc udowodnić tylko fakt jednoznaczności takiego iloczynu dla każdej liczby złożonej.
Załóżmy nie wprost, że istnieje liczba naturalna, która ma dwa różne rozkłady na czynniki pierwsze.

Wówczas istnieje najmniejsza taka liczba (z ograniczenia zbioru liczb naturalnych). Oznaczmy ją jako \(\displaystyle{ n}\).

\(\displaystyle{ n = p_1 p_2 \cdot \dots \cdot p_k = q_1 q_2 \cdot \dots \cdot q_t}\) (gdzie \(\displaystyle{ k,t}\) naturalne)

Fakt: Z minimalności \(\displaystyle{ n}\) wiemy, że żadna liczba z \(\displaystyle{ p_1 p_2 \cdot \dots \cdot p_k}\) nie powtarza się w \(\displaystyle{ q_1 q_2 \cdot \dots \cdot q_t}\) (bo wówczas moglibyśmy jest skrócić).

Liczba \(\displaystyle{ p_1}\) oczywiście dzieli \(\displaystyle{ n}\). W takim razie \(\displaystyle{ p_1}\) dzieli również\(\displaystyle{ q_1 q_2 \cdot \dots \cdot q_t}\) co jest sprzeczne z powyższym Faktem.