Na wikipedi znajduje się wyżej wymieniony dowód ( 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 .
dowód algorytmu euklidesa wikipedia
dowód algorytmu euklidesa wikipedia
Ostatnio zmieniony 29 cze 2011, o 07:52 przez Qń, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Nawet proste wyrażenia matematyczne umieszczaj w klamrach[latex]...[/latex]
Powód: Poprawa wiadomości. Nawet proste wyrażenia matematyczne umieszczaj w klamrach
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
dowód algorytmu euklidesa wikipedia
Chyba raczej większa od \(\displaystyle{ d}\). Gdyby istniała, to mielibyśmy: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}\) .
\(\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.