Algorytm Euklidesa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
myszka9
Użytkownik
Użytkownik
Posty: 1185
Rejestracja: 13 paź 2012, o 17:34
Płeć: Kobieta
Lokalizacja: tu i tam
Podziękował: 528 razy
Pomógł: 5 razy

Algorytm Euklidesa

Post autor: myszka9 »

\(\displaystyle{ NWD(5, -65537) = 1}\)

\(\displaystyle{ -65537 = 5 \cdot (-13108) + 3}\)

\(\displaystyle{ 5 = 3 \cdot 1 + 2}\)

\(\displaystyle{ 3 = 2 \cdot 1 + 1}\)

\(\displaystyle{ 2 = 1 \cdot 2 + 0}\)

Wyliczam \(\displaystyle{ Za}\) i \(\displaystyle{ Zb}\), gdzie \(\displaystyle{ NWD(a,b) = Za \cdot a + Zb \cdot b}\)

\(\displaystyle{ $\begin{align*}1 &= 3 -(1)2 = 3 -(1)(5-(1)3) = 2 \cdot 3 + (-1)5 \\
&= 2(-65537 - (-13108)5) + (-1)5 = 2(-65537) + 9 \cdot (13108).\end{align*}$}\)


Gdzie mam błąd?
Ostatnio zmieniony 1 lis 2012, o 23:17 przez Sylwek, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Sylwek
Użytkownik
Użytkownik
Posty: 2716
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 160 razy
Pomógł: 657 razy

Algorytm Euklidesa

Post autor: Sylwek »

Ostatnia równość, coś tam pomieszałaś, powinno być \(\displaystyle{ = 2 \cdot (-65537) + 5 \cdot 26215}\).
myszka9
Użytkownik
Użytkownik
Posty: 1185
Rejestracja: 13 paź 2012, o 17:34
Płeć: Kobieta
Lokalizacja: tu i tam
Podziękował: 528 razy
Pomógł: 5 razy

Algorytm Euklidesa

Post autor: myszka9 »

A może po prostu zapomniałam o świecie w jakim się znajduje?

\(\displaystyle{ -65537 = 0}\) w \(\displaystyle{ Z_{65537}}\) ?
Awatar użytkownika
Sylwek
Użytkownik
Użytkownik
Posty: 2716
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 160 razy
Pomógł: 657 razy

Algorytm Euklidesa

Post autor: Sylwek »

myszka9 pisze:\(\displaystyle{ -65537 = 0}\) w \(\displaystyle{ Z_{65537}}\) ?
Tak, ale równość \(\displaystyle{ NWD(a,b)=xa+yb}\) to zwykła równość algebraiczna nad \(\displaystyle{ \ZZ}\), więc tu już nic nie upraszczaj (chyba, że np. szukasz \(\displaystyle{ 5^{-1}}\) w \(\displaystyle{ Z_{65537}}\), wówczas to oczywiście będzie \(\displaystyle{ 26215}\)).
myszka9
Użytkownik
Użytkownik
Posty: 1185
Rejestracja: 13 paź 2012, o 17:34
Płeć: Kobieta
Lokalizacja: tu i tam
Podziękował: 528 razy
Pomógł: 5 razy

Algorytm Euklidesa

Post autor: myszka9 »

Liczę, liczę i nie mogę się doliczyć \(\displaystyle{ Za, Zb}\). Jak Ci to wyszło to \(\displaystyle{ Zb = 5}\).-- 2 lis 2012, o 19:45 --Ok! Już wiem . Wyliczałam \(\displaystyle{ Zb}\) , nie patrząc na \(\displaystyle{ b}\) , tylko na wielokrotność \(\displaystyle{ a}\).
ODPOWIEDZ