kongruencje popek: Może mi ktoś wytłumaczyć skąd się bierze to w kongruencjach: Mam takie coś: 13x=16(mod 47) NWD(13,47)=1 1=5*47−18*13 13⁻¹(mod47) = −18 = 29(mod47) Nie wiem skąd dokładnie się bierze to: 29(mod47)

Basia: −18 = −1*47 + 29

popek: Okej, a póxniej x=16*29(mod 47) x = 464 = 41(mod 47) skąd to:41(mod 47) I jak później do teog sprawdzenie zrobić?

Basia: 464:47 = 9 reszta 41

popek: o Cie Panie.... Mogłabyś mi wytłumaczyć dlaczego tak to się wszystko robi? Mam w zeszycie zapisane, że: ax = b(modm) x=b*a⁻¹(modm) Widze, ze to sa proste działania, ale dlaczego tak to nie mam pojecia.

Basia: ale coś mi tu nie gra; sam to robiłeś?

popek: Co dokładnie? Nie, to jest przykład z ćwiczeń.

Basia: a nie dobrze jest; pomyliłam się w mnożeniu

popek: Mogłabyś mi powiedzieć jak się robi sprawdzenie do tego? Reszte już sam ogarne.

Basia: szukasz elementu odwrotnego do 13 (mod 47) czyli takiego aby 13*y = 1 (mod47) 1 = 1*47 − 46; 46 niepodzielne przez 13 1 = 2*47 − 93; 93 niepodzielne przez 13 1 = 3*47 − 140; 140 niepodzielne przez 13 1 = 4*47 − 187; 187 niepodzielne przez 13 1 = 5*47 − 234 = 5*47 − 18*13 −18 = −1*47+29 czyli 13⁻¹=29 (mod 47) mniej więcej na tym to polega

popek: dziekuje bardzo.

Basia: sprawdzenie: 13*41=533 533/47 = 517 r.16 czyli 533 = 16 (mod 47) czyli 13*41 = 16 (mod 47)