dowód algorytmu euklidesa wikipedia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
kos-a
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 28 cze 2011, o 23:40
Płeć: Mężczyzna
Lokalizacja: Kraków

dowód algorytmu euklidesa wikipedia

Post autor: kos-a » 29 cze 2011, o 00:02

Na wikipedi znajduje się wyżej wymieniony dowód (http://pl.wikipedia.org/wiki/Algorytm_Euklidesa) i w związku z tym chciałem zapytać o pewną rzecz która nie daje mi spokoju.
Jak spojrzymy na ten fragment dowodu który wymaga udowodnienia lematu:
\(\displaystyle{ NWD(a,b ) = NWD ( b ,a mod b )}\)
To zastanawia mnie czy w kilku następnych linijkach nie trzeba udowodnić że , \(\displaystyle{ t}\) i \(\displaystyle{ s-pt}\) to liczby względnie pierwsze i to dopiero pozwoli nam potwierdzić słuszność lematu .
Bo może ja ten dowód źle rozumiem ale wydaje mi się ,że tak udowadniamy tylko że skoro \(\displaystyle{ NWD(a,b) = d}\) i \(\displaystyle{ (a mod b)}\) jest podzielne przez \(\displaystyle{ d}\) to wcale nie oznacza że \(\displaystyle{ NWD (b ,a mod b ) =d}\) . Bo może akurat istnieje liczba \(\displaystyle{ k}\) większa od \(\displaystyle{ 1}\) i całkowita taka ,że \(\displaystyle{ t = km}\) i \(\displaystyle{ s-pt = kn}\) .
Gdyby ktoś mógł mi pokazać jak wykazać ,że powyższe liczby są wzglednie pierwsze to będe naprawdę kontent .
Mam nadzieje , że ktoś zada sobie trud przeanalizowania mego toku rozumowania choć niewątpliwie będzie to trudne .
Ostatnio zmieniony 29 cze 2011, o 07:52 przez , łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Nawet proste wyrażenia matematyczne umieszczaj w klamrach [latex]...[/latex]

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

dowód algorytmu euklidesa wikipedia

Post autor: » 29 cze 2011, o 08:00

kos-a pisze:może akurat istnieje liczba \(\displaystyle{ k}\) większa od \(\displaystyle{ 1}\) i całkowita taka ,że \(\displaystyle{ t = km}\) i \(\displaystyle{ s-pt = kn}\) .
Chyba raczej większa od \(\displaystyle{ d}\). Gdyby istniała, to mielibyśmy:
\(\displaystyle{ s=pt+kn=pkm+kn=k(pm+n)}\)
czyli dzieliłaby nie tylko \(\displaystyle{ t}\), ale także \(\displaystyle{ s}\), czyli byłaby ich wspólnym dzielnikiem większym od \(\displaystyle{ d}\), wbrew temu, że \(\displaystyle{ d}\) jest największym.

To samo rozumowanie można przedstawić zgrabniej, to znaczy wykazać (tak samo), że:
\(\displaystyle{ k|a \wedge k|b \Leftrightarrow k|b \wedge k|(a modb)}\)
a potem stwierdzić, że oznacza to iż wspólne dzielniki liczb \(\displaystyle{ a,b}\) oraz liczb \(\displaystyle{ b,amodb}\) są takie same, a zatem największe wspólne dzielniki też są takie same.

Powodzenia jutro na egzaminie ;).

Q.

kos-a
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 28 cze 2011, o 23:40
Płeć: Mężczyzna
Lokalizacja: Kraków

dowód algorytmu euklidesa wikipedia

Post autor: kos-a » 29 cze 2011, o 15:00

Dzięki , w końcu to rozumiem .

ODPOWIEDZ