euklides
Kamil: Oblicz
NWD(263−1,291−1)
Pewnie tu trzeba algorytm euklidesa modulo, tylko w internecie nie mogę znaleźć jakoś dobrze
wytłumaczone.,
Pomógłby ktos?
12 mar 22:09
jc:
nwd(263−1, 291−1)=nwd(263−1, 291−263)
=nwd(263−1, 263(228−1))=nwd(263−1, 228−1)
itd.
12 mar 22:34
Blee:
krok 1.
291 − 1 = (263 − 1)*228 + 228 − 1
(291 − 1) (mod (263 − 1) = 228 − 1
krok 2.
263 − 1 = (228 − 1)*235 + 235 − 1 = (228 − 1)*235 + (228 − 1)*27 + 27 −1
(263 − 1) (mod (228 − 1) = 27 − 1
krok 3.
228 − 1 = (27 − 1)*221 + (27 −1)*214 + (27 − 1)27 + 27 − 1 =
= (27−1)27(23 + 22 + 1)
12 mar 22:39
Kamil: może zadam teraz banalne pytanie, ale jednej rzeczy nie rozumiem.
Jc
Dlaczego w drugiej linijce tj.
nwd(263−1,263(228−1))=(263−1,228−1)
dlaczego tak po prostu znika to 263 które zostało wyjęte przed nawias?
12 mar 22:45
Blee:
263(228−1) = 263(228−1) − (228−1) + (228−1) =
= (263−1)(228−1) +(228−1)
12 mar 22:47
Basia:
bo 2
63 ma w rozkładzie same dwójki, a 2
63−1 jest nieparzysta
na pewno nie mają wspólnego dzielnika
12 mar 22:47
Kamil: Czyli w takiej sytuacji mogę zrobić coś takiego?
Przykład()
NWD(107,88*21 )=NWD(107,21)?
na mocy jakiego prawa?
12 mar 22:56
Adamm:
musisz najpierw rozłożyć 88 na czynniki pierwsze, by sprawdzić czy żaden z nich
nie dzieli 107
12 mar 22:57
Basia: no nie; w rozkładzie 88 masz 2*44=22*21 = 22*3*7
NWD(107; 88*21) = NWD(107; 22*3*7*3*7) = NWD(107; 22*32*72)
w rozkładzie 107 nie ma ani 2, ani 3 (7 też nie, ale to już trzeba dzielić)
a poprzednie powinieneś wiedzieć z praw podzielności
NWD = NWD(107, 72)
12 mar 23:02
Kamil: a nie mógłbym nawet tą 72 usunąć i zostawić tak NWD(107,1)?
12 mar 23:06
Adamm:
jeśli NWD(a, c)=1 to
NWD(a, c*b)=d
jest największą liczbą że d|a oraz d|c*b
w szczególności NWD(d, c)=1, gdyby było >1 to znaczyłoby że znajdziemy m|d oraz m|c oraz m>1
skąd m|d oraz d|a wynika m|a
co przeczyłoby NWD(a, c)=1
skoro d i c są względnie pierwsze, to d|c*b ⇔ d|b
stąd
d=NWD(a, b)
12 mar 23:09
Kamil: czyli w tym zadaniu odpowiedź to NWD= 27−1?
12 mar 23:16
Basia: @Kamil oczywiście przecież widzimy, że 107 nie dzieli się przez 7
przy takich małych liczbach (bez potęg i innych utrudnień) w sumie łatwiej znaleźć ten NWD
rozkładając liczby na czynniki niż stosując algorytm Euklidesa
(chociaż nie zawsze, bo jak mamy duże liczby pierwsze, narobimy się strasznie, Euklides lepszy)
ale jak masz takie coś z potęgami (jak wcześniej) to już tak nie pójdzie
12 mar 23:18
Basia: zgubiłam się; w którym?
12 mar 23:19
Kamil: na początku tematu, zrobiłem tym sposobem, ale może gdzieś się pogubiłem
NWD(263−1,291−1)=NWD(263−1,228−1)=NWD(235−1,228−1)=
NWD(27−1,228−1)=NWD(27−1,221−1)=NWD(27−1,27−1)=
12 mar 23:25
Basia:
263−1 − 228+1 = 228(235−1)
NWD(228(235−1);228−1) = NWD(235−1); 228−1}=
NWD(228(27−1); 228−1} = NWD(27−1; 228−1}
228−1 = (214−1)(214+1} = (27−1)(27+1)(214+1)
tak; NWD = 27−1
12 mar 23:27
Kamil: Wielkie dzięki Basia, jc i wszystkim którzy pomagali.
12 mar 23:31