\(\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?
Algorytm Euklidesa
- Sylwek
- 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
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 pisze:\(\displaystyle{ -65537 = 0}\) w \(\displaystyle{ Z_{65537}}\) ?
-
- 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
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}\).