kongruencja kombinator: Rozwiąż kongruencję 21x ≡ 5 (mod 36) mam do zrobienia 16 przykładów, czy ktoś móglby mi pokaząć jak ro ruszyć ?

Jack: nie znam sie za bardzo na tym, ale na czysta logike... 21x ≡ 5 (mod 36) czyli 21x = k*36 + 5 a tu juz widac, ze szukamy takich liczb, ze NWD(21,36) = 5

Mila: Brak rozwiązania . Lewa strona podzielna przez 3 , a prawa nie 21x=36k+5 Pisz następną kongruencję.

kombinator: 3x ≡ 59 (mod 100)

Jack: oczywiscie tam gafe walnalem 22:33 NWD(21,36) ≠5

Adamm: 3x≡−141 mod 100 x≡−47 mod 100 x≡53 mod 100

Jack: @Adamm "rozbudowujemy" tak dlugo, aby moc podzielic bez reszty liczbe przy "x" ?

Adamm: nie wiem, ja tak robię bo działa

Jack: czyli obstawiam ze tak

Jack: nastepne!

kombinator: czy zawsze można dzielić kongruencję ?

kombinator: 99x≡ 1 (mod13)

Mila: Rozszerzony algorytm Euklidesa: 3x=59(mod 100) 100=3*33+1 1=100*1−33*3 odwrotna do 3 w Z₁₀₀ to (−33) −33+100=67 3x=59(mod100) /*67 201x=3953(mod100)⇔ x=53(mod100)

Adamm: 99x≡27 mod 13 11x≡3 mod 13 11x≡55 mod 13 x≡5 mod 13

kombinator: Mila: ja nie rozumiem jak to można zrobić z Euklidesa.Ja umiem Euklidesa tylko robiąc tą tabelkę. Z niej otrzymuje rezultatl 53x+3y=53*(−1)+3*20 i nie wiem co z tym zrobić

Mila: 99x=1 (mod13) 99=7*13+8 Równanie możemy zapisać: 8x=1(mod13) 13 jest małą liczbą możesz znaleźć odwrotną mnożąc 8 kolejno przez 1,2,3,4,..12 8*2=16=3(mod13) 8*3=24=11(mod13) 8*4=32=6(mod13) 8*5=40= 1(mod13) x=5(mod13) Albo rozszerzony A.E.

KKrzysiek: 3x=59 (mod 100) można zauważyć, że 3x=100y+59 3x−100y=59 teraz szukasz NWD(3,−100) −100 = 3* (−34) + 2 3 = 2*1 +1 2 = 1*2+0 NWD(3,−100) = 1 szukasz takiego Z_a, Z_b ∊ Z, że NWD(..,..) = Z_a*a+Z_b*b 1= NWD(..) = 3−2 = 3−(−100+3*34) = 3+100−3*34 = 100*1+3*(−33) −33 + 100 = 67

kombinator: a np 17x ≡ 1(mod26)

KKrzysiek: Szukasz tak samo 17x =26y+1 17x−26y=1 NWD(17,−26) −26 =17*(−2) +8 17 = 8*2 +1 8 = 1 *8+0 NWD(...) = 1 1=NWD(...)=17−8*2 = 17−(−26+17*2)*2 = −17*3 +26*2 = 17*(−3) +26*2 −3+26 = 23 bo 23*17 mod 26 = 1

Adamm: 17x≡1 mod 26 17x≡391 mod 26 x≡23 mod 26

KKrzysiek: Zresztą przeszukaj moje posty, ja tam pisałem o kilku sposobach wyznaczania el. odwrotnego. Może znajdziesz.

kombinator: Kkrzysiek ale skąd Ty bierzesz te liczby bo ja nigdy czegoś takiego nie robiłem więc nie wiem

KKrzysiek: Które liczby?

KKrzysiek: 17x ≡ 1(mod26) Wiemy, że w ciałach wykonujemy działanie modulo. Dlatego można powiedzieć, iż 17x to jakaś tam liczba, a 1 to reszta z dzielenia 17x przez 26. I ile razy 26 mieści się w tej liczbie oznaczamy sobie przez y.

Mila: Tu popatrz− ćwiczenie 3 i 4. http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/%C4%86wiczenia_10:_Teoria_liczb

KKrzysiek: W wyniku czego otrzymujemy równanie diofantyczne, rozwiązujesz je sposobem poznanym na zajęciach.

kombinator: 12x ≡ 8 (mod2)

KKrzysiek: Po co wrzucasz kolejny przykład, że niby mamy go zrobić? Spróbuj teraz sam.

Jack: jak coś może dać reszte 8 z dzielenia przez 2 ?

Mila: 12x ≡ 8 (mod2)=0(mod2)⇔ 12x=0(mod2)

Mariusz: U Cormena "Wprowadzenie do algorytmów " masz pseudokod rozszerzonego algorytmu Euklidesa niestety u nich masz wersję rekurencyjną oraz działającą tylko dla liczb nieujemnych