Podstawowe twierdzenie arytmetyki - dowód

[tranto]

Czy istnieje bardziej przystępny dowód zasadniczego twierdzenia arytmetyki niż ten podany na polskiej Wikipedii?

[janusz47]

Istnieje szereg dowodów tego twierdzenia,
Proponuję dowód Pana Prof. Wacława Sierpińskiego w jego książce Arytmetyka Teoretyczna, PWN Warszawa.

[OQO]

Ja znam taki, prosze mnie poprawic jezeli sie myle:

Pokazanie ze w ogole istnieje rozklad na pierwsze jest bardzo latwe przez indukcje. Teraz jezeli \(\displaystyle{ n=2}\) to w oczywisty sposob rozklad jest jednoznaczny. Zakladamy ze pokazalismy twierdzenie dla wszystkich liczb \(\displaystyle{ 2,3,...,n-1}\) (to jest jedna z rownowaznych wersji tw o indukcji matematycznej, znacznie bardziej wygodna tutaj). Teraz patrzymy na \(\displaystyle{ n}\) i rozkladamy na czynniki pierwsze. Zeby pokazac ze rozklad jest jednoznaczny, zakladamy ze nie jest:

\(\displaystyle{ n=p_1 ... p_s = q_1 ... q_t}\).

Widac stad ze \(\displaystyle{ p_1}\) dzieli \(\displaystyle{ n}\), czyli dzieli iloczyn \(\displaystyle{ q_1 ... q_t}\), czyli dzieli ktorys z jego czynnikow, rownie dobrze moze byc to \(\displaystyle{ q_1}\). Ale \(\displaystyle{ p_1, q_1}\) sa obie pierwsze, wiec z tej podzielnosci wynika ich rownosc. Dlatego mozemy skrocic stronami przez \(\displaystyle{ p_1}\):

\(\displaystyle{ \frac{n}{p_1} = p_2 ... p_s = q_2 ... q_t}\)

Ale \(\displaystyle{ 1<\frac{n}{p_1}<n}\) wiec mozna skorzystac z zalozenia indukcyjnego, stad rozklad jest jednoznaczny co konczy dowod.

[Ponewor]

W dziele pod tytułem: "Wstęp do teorii liczb" Wacława Sierpińskiego jest zdaje się ten sam, albo bardzo podobny dowód tego twierdzenia co na Wikipedii, co mogłem sprawdzić jeszcze szybciej zerkając w przypisy artykułu na WIKI.

Istnieje szereg dowodów tego twierdzenia,
Proponuję dowód Pana Prof. Wacława Sierpińskiego w jego książce Arytmetyka Teoretyczna, PWN Warszawa.

Zajrzałem na krótko i tutaj tego dowodu nie widzę.

[Zordon]

Ja znam taki, prosze mnie poprawic jezeli sie myle:

Pokazanie ze w ogole istnieje rozklad na pierwsze jest bardzo latwe przez indukcje. Teraz jezeli \(\displaystyle{ n=2}\) to w oczywisty sposob rozklad jest jednoznaczny. Zakladamy ze pokazalismy twierdzenie dla wszystkich liczb \(\displaystyle{ 2,3,...,n-1}\) (to jest jedna z rownowaznych wersji tw o indukcji matematycznej, znacznie bardziej wygodna tutaj). Teraz patrzymy na \(\displaystyle{ n}\) i rozkladamy na czynniki pierwsze. Zeby pokazac ze rozklad jest jednoznaczny, zakladamy ze nie jest:

\(\displaystyle{ n=p_1 ... p_s = q_1 ... q_t}\).

Widac stad ze \(\displaystyle{ p_1}\) dzieli \(\displaystyle{ n}\), czyli dzieli iloczyn \(\displaystyle{ q_1 ... q_t}\), czyli dzieli ktorys z jego czynnikow, rownie dobrze moze byc to \(\displaystyle{ q_1}\). Ale \(\displaystyle{ p_1, q_1}\) sa obie pierwsze, wiec z tej podzielnosci wynika ich rownosc. Dlatego mozemy skrocic stronami przez \(\displaystyle{ p_1}\):

\(\displaystyle{ \frac{n}{p_1} = p_2 ... p_s = q_2 ... q_t}\)

Ale \(\displaystyle{ 1<\frac{n}{p_1}<n}\) wiec mozna skorzystac z zalozenia indukcyjnego, stad rozklad jest jednoznaczny co konczy dowod.

Niestety jest tutaj luka. Korzystasz z tego, że jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli \(\displaystyle{ ab}\) to \(\displaystyle{ p|a \vee p|b}\), należy to najpierw udowodnić.

[justynian]

Przystępny dowód tego twierdzenia można znaleźć w "co to jest matematyka".

[OQO]

Niestety jest tutaj luka. Korzystasz z tego, że jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli \(\displaystyle{ ab}\) to \(\displaystyle{ p|a \vee p|b}\), należy to najpierw udowodnić.

No tak, to wymaga paru krokow wstecz : dowod tego wynika z faktu, ze \(\displaystyle{ d \mid qn \Rightarrow d \mid n}\) jesli \(\displaystyle{ nwd(d,q)=1}\), co z kolei wynika z rozkladu \(\displaystyle{ nwd(a,b) = ax+by}\) dla pewnych \(\displaystyle{ x,y}\) co pokazuje sie przez indukcje na \(\displaystyle{ a+b}\).

[Zordon]

No tak, to wymaga paru krokow wstecz : dowod tego wynika z faktu, ze \(\displaystyle{ d \mid qn \Rightarrow d \mid n}\) jesli \(\displaystyle{ nwd(d,q)=1}\), co z kolei wynika z rozkladu \(\displaystyle{ nwd(a,b) = ax+by}\) dla pewnych \(\displaystyle{ x,y}\) co pokazuje sie przez indukcje na \(\displaystyle{ a+b}\).

Masz rację. Jednak mówienie indukcja "na", bądź też indukcja "po" (chociaż ta wersja jest jeszcze znośna) jest przez niektóre osoby uznawane za poważne przestępstwo. Polecam raz na zawsze przyzwyczaić się do indukcji "względem".

[MadJack]

A mógłby ktoś napisać zarys tego, jak się dowodzi to indukcyjnie? Byłbym wdzięczny, bo mnie to zaciekawiło

[Zordon]

Indukcyjnie to ja nie lubię. To jest po prostu rozszerzony algorytm Euklidesa, trzeba udowodnić poprawność. Można znaleźć w wielu miejscach.

[MadJack]

Aha, to znam Też ten dowód średnio lubię. Ale i tak dzięki