Algorytm euklidesa.

Finarfin · Post autor: **Finarfin** » 21 cze 2007, o 23:24

Mam zadanie. Zastosować rozszerzony algorytm euklidesa do rozwiązania układu:
\(\displaystyle{ 7x \equiv 2(mod 15)}\)
Dlaczego ta kongruencja ma rozwiązanie?

Prosiłbym o krok po kroku, nigdzie nie mogłem znaleźć fachowego opisu tego typu przykładów przy zastosowaniu algorytmu euklidesa...

Edit: jeszcze jedno:
Korzystajac z rozszerzonego algorytmu Euklidesa obliczyc element odwrotny do
\(\displaystyle{ a = 343 Z_{1734}}\). Z jakiego twierdzenia wynika istnienie tego elementu odwrotnego?

bondyros · Post autor: **bondyros** » 22 cze 2007, o 21:33

szczerze mowiac nie mam pojecia jak wyglada ROZSZERZONY algrotym Euklidesa...rowiazanie problemu tego tym algorytmem z ktorym ja sie spotkalem wyglada nastepujaco:
7X+15Y=2 ;

Y X
15 1 0
7 0 1 (-2)
1 1 -2

czyli z algorytmu Euklidesa wynika, ze: 7*(-2)+15*1 = 1
czyli 7*(-4)+15*2 = 2 => -4 (mod15) = 11 +15k, k nalezy do calkowitych

kongruencja posiada rozwiazanie poniewaz - (7,15)|2 , oczywiscie (7,15)=1

drugi problem - tworzysz kongruencje

343*b = 1 (mod1734)

stosujesz tak samo algorytm euklidesa by wyliczyc "b" i "c" w rownaniu:

343*b + 1734*c = 1;

c b
1734 1 0
343 0 1 (-5)
19 1 -5 (-18)
1 -18 91

czyli: 1734*(-18) +343*91 = 1 => 343*91 = 1 (mod 1734) czyli element odwrotny do 343 w Z (1734) wynosi 91

dlaczego istnieje? z tej samem przyczyny co wczesniej czyli (1734,343)|1 - albo jak wolisz 1734 i 343 sa wzglednie pierwsze (tylko wtedy element 343 moze miec elemnt odwrotny w jakims ciele)

Emiel Regis · Post autor: **Emiel Regis** » 22 cze 2007, o 21:55

bondyros pisze: dlaczego istnieje? z tej samem przyczyny co wczesniej czyli (1734,343)|1 - albo jak wolisz 1734 i 343 sa wzglednie pierwsze (tylko wtedy element 343 moze miec elemnt odwrotny w jakims ciele)

W ciele każdy element różny od zera ma element odwrotny ; )
\(\displaystyle{ Z_{1734}}\) nie jest ciałem rzecz jasna jednak tak jak poprzednik wyjasnił 343 oraz 1734 są to liczby względnie pierwsze. To wystarczy.

bondyros · Post autor: **bondyros** » 22 cze 2007, o 22:10

faktycznie to nie jest cialo --- ehhh Algebry jednak juz nie pamietam:)

[ Dodano: 22 Czerwca 2007, 22:11 ]
no ale pomijajac szczegoly wszystko jasne powinno byc:)

Finarfin · Post autor: **Finarfin** » 23 cze 2007, o 13:49

Generalnie wielkie dzięki, mniej więcej kojarzę, tylko tej tabelki jeszcze nie czaję. Możecie ją bardziej szczególowo opisać?

No i szkoda, że przedwczoraj odpowiedzi nie dostałem, wtedy bym pewnie na egzaminie zrobił to proste zadanie(akurat jedyne, którego nie zrobiłem :/):

Zastosuj rozszerzony algorytm euklidesa do obliczenia elementu odwrotnego \(\displaystyle{ a=12 Z_{37}}\) Dlaczego ten element odwrotny istnieje?

Wydaje się jeszcze prostsze...

bondyros · Post autor: **bondyros** » 23 cze 2007, o 14:01

finarfin --- dlaczego to juz wiesz:)

tableka -- oki

masz rownanie : 37X +12Y=1
_____ X___Y_____ i dokonujesz operacji 37+12*(-3) ; 1 + 0*(-3); 0+1*(-3)
koniec algorytmu poniewaz w nastepnej linijce mialbys 0!!
i odczytujesz tak jak wczesniej, ze ----- 1=37X+12Y czyli 1=37*1+12*(-3) !!!!
czyli element odwrotny do 12 w Z37 to jest -3 (mod 37) = 34 koniec zadania

ps. no coz --- trzeba bylo szybciej napisac posta:) albo lepiej, szybciej mnie tu zwerbowac;P

Finarfin · Post autor: **Finarfin** » 23 cze 2007, o 14:15

bondyros, dzięki wielkie, już kapuję :]

No trudno - piątki nie będzie Teraz tylko żal, że się nie wiedziało jak rozwiązać najprostsze zadanie(bo tak to wygląda )

Xitami · Post autor: **Xitami** » 25 cze 2007, o 13:31