. asdf: Cześć, jak takie cos rozwiazac? 25X ≡ 12 mod 17? da się to zrobić rozszerzonym algorytmem Euklidesa?

asdf: :(

Mila: Tak, znajdź odwrotną do 25 w Z₁₇ i pomnóż obie strony równania przez tę odwrotność.

asdf: Ok, to mam takie rownanie: 25X + 17K = 1 K=2 25X + 34 = 1 34 = 25 + 9 25 = 2*9 + 7 9 = 7*1 + 2 7 = 3*2 + 1 1 = 7−3*2 = 7 − 3*(9−7) = 7 − 3*9 + 3*7 = 4*7 − 3*9 = 4*(25−9*2) − 3*9 = 4*25 − 8*9 − 3*9 = 4*25 − 11*9 = 4*25 − 11*(34 − 25) = 4*25 − 11*34 + 11*25 = 15*25 − 11*34 a więc el. odwrotnym dla 25 w Z₁₇ jest 15, tak też można czy to "przypadek", ze mi wyszlo? teraz mam pomnozyc rownanie przez te odwrotnosc, czyli: 25X * 15 ≡ 12*15 mod 17 ?

kyrtap: sory że pytam ale co to jest te mod bo zawsze mnie zastanawiało

asdf: reszta z dzielenia

kyrtap: czemu ją tak zapisujecie?

asdf: 5 mod 2 = 1 5 mod 3 = 2 7 mod 9 = 9 14 mod 9 = 5 itd..

asdf: a jak mam zapisywac? tak: %? ... dla mnie malo to czytelne ale to tylko moje zdanie

Kacper: 25x≡12 (mod 17) 25⁻¹≡15 (mod 17) 15*25x≡12*15 (mod 17) 375x≡180 (mod 17) x≡10 (mod 17)

asdf: właśnei udalo mi sie to zrobić, dzięki

Mila: 25x=12(mod17)⇔ 8x=12(mod17) 17=2*8+1 1=1*17−2*8 −2 +17=15 8x=12(mod17) /*15 1x=180 (mod17) x=10 (mod17)

asdf: można krócej, wymaga to troche doswiadczenia dzieki!

Mila:

Saizou: albo tez podzielic przez 4 w momencie 8x=12 mod 17 2x=3 mod 17 2x=−14 mod 17 x=−7 mod 17

asdf: Dzieki! ale mozna podzielic przez 4 bo NWD(4,17) = 1?

Saizou: tak, nie zmieniasz modulu bo nwd(17, 4)=1 jesli by wynosilo wiecej niz 1 to muszi podzielic modul przez nwd

asdf: ok, teraz takie cos: 3X + 2 = 1 mod 5 // + 3 3X + 5 = 4 mod 5 3X = 4 mod 5 3⁻¹ = 2 2*3X =8 mod 5 6X = 8 mod 5 X = 8 mod 5 X = 3 mod 5 X = 3 Ok? Jeszcze pytanie: mozna dodawac i odejmowac jaka sie chce wartosc tak?

Saizou: tak, i jest ok

Mila: Tak, byle prowadziło do celu. np. 3x+2=1(mod5) /−2 3x=−1 (mod5) /*2 6x=−2 (mod5) 1x=−2(mod(5) x=3 (mod5)

asdf: o, fajne Dzieki Wam

asdf: Macie moze jakis zbior zadan z kongruencja? (teraz mi sie trafil taki przedmiot, ze mam troche arytmetyki modularnej − kryptografia i z checia wrocilbym do matmy )

asdf: " asdf: Dzieki! ale mozna podzielic przez 4 bo NWD(4,17) = 1? Saizou: tak, nie zmieniasz modulu bo nwd(17, 4)=1 jesli by wynosilo wiecej niz 1 to muszi podzielic modul przez nwd " czyli zawsze sie dzieli przez NWD, tylko z automatu nie robi sie tego dla jedynki

Kacper: Ogólnie można dodawać, odejmować, mnożyć zawsze. Dzielić już nie

Mila: Ja w ogóle nie dzielę.

Saizou: mozemy to udowodnic, znaczy sie dzielenie xd ale to jak bede na kompie

Kacper: Mila ja także (bo czasem zapominać kiedy można )

asdf: po co dzielic, skoro mozna pomnozyc

Saizou : bo co to jest dzielenie ? mnożenie przez odwrotnośc

asdf: przy mnozeniu nie ma zadnych dodatkowych regul? bo z tego wzoru: (a*b) mod n = [a mod n * b mod n] mod n nie wiele "widac" a == b mod n n | (a−b) ak == bk mod n => n | k*(a−b) iii...wnioskuje, ze nie ma, racja?

Saizou : łap taką kongruencję 2x≡7 (mod 10)

Saizou : nl a−b a−b=nk pa−pb=pnk czyli nl pa−pb a to jest rownoważne z pa=pb mod n

Kacper: Brak rozwiązań! Nie ładnie

Saizou : Kacper to nie było dla Ciebie

asdf: NWD(2,10) | 7 => dupa, nie uda sie.

Saizou : Oblicz ostatnie 2 cyfry liczby 12397²⁰⁴⁴

asdf: 12397²⁰⁴⁴ mod 100...masz! a tak serio − od czego zaczac?

Saizou : 12397=97=−3 mod100 i chyba szwajcarski matematyk

Kacper: czyżby 81?

Saizou : Kacper nie psuj zabawy

Mila: Kacper, wychodzimy!.

Saizou: zostancie, ja i tak jestem na tele wiec niezbyt wygodnie mi sie pisze

Kacper: Mila jaką herbatkę preferujesz?

asdf: nie, czemu "wychodzimy", przeciez to tylko wynik... mnie to nie za wiele urzadza zaraz rozkminie, wczoraj siedzialem nad takim wzorem: a^Φ(n) mod n = 1, gdy NWD(a,n) = 1, wiec pewnie tutaj cos jest... n = 100, NWD(12397,100) = 1...chyba musze policzyc Φ(100)...zaraz poszukam wzoru na to

Mila: Dilmah+Ceylon.

Saizou: po dzielnika pierwszych go poznacie xd

asdf: Φ(100) = Φ(10²) = Φ(2²*5²) = 2²⁻¹*(2−1) * 5²⁻¹*(5−1) = 2¹*1*5¹*4 = 40, ok? Φ(100) = 40 2044 = 2040/40*40 + 4 = 51*40+4 12397^51*40+4 mod 100 = 12397⁴*1⁵¹ mod 100 = ...? ok licze?

Saizou: jest ok ale to nie koniec

Mila: NWD(12397,100)=NWD(12397, 2²*5²)=1

asdf: a to jest prawdziwe? 12397⁴ mod 100 = (12300+97)⁴ mod 100 = 97⁴ mod 100

Saizou: tak, mozesz to sobie wyprowadzic, ojojo... zaczynam mowic ja matematyk xd

asdf: Mila, z jakiego warunku sie to wzielo? co dalo "2² * 5²" ?

Saizou: to jest rozklad 100 z pta

asdf: zachodzi cos takiego? a^k mod n = (a mod n)^k mod n,czyli to jest wlasnie sobie te wyprowadzenie?

Mila: 100=4*25=2²*5² rozkład na czynniki pierwsze. W tej sytuacji 12397 nie rozkładam, bo nie dzieli się ani przez 2 ani przez 5 .

Saizou: nie o tym myslalem, jutro pokaze co mialem na mysli

asdf: to moze byc dobre rozwiazanie? (12300+97)⁴ mod 100 = 97⁴ mod 100 = (97² mod 100)² mod 100 = (9409 mod 100)² mod 100 = 9² mod 100 = 81 kóniec?

asdf: zrobilem to troche "rekurencyjnie", ale czy jest takie cos prawidlowe...

Saizou: mogles odwrocic 97 na −3 i miec x=(−3)⁴ mod100

asdf: moooglem masz jeszcze?

Saizou : Rozwiąż równanie w ℤ 213x − 144y = 12.

asdf: momencik

Saizou : skorzystaj z kongruencji

asdf: cicho!

asdf: 213X = 12 mod 144?

Saizou : tak

asdf: 213X = 12 mod 144 69 = 12 mod 144 NWD(3, 144) = 3 144/3 = 48 23X = 4 mod 48 23X + 48y = 4 z rozszerzonego algorytmu policzylem, ze dla 23 mod 48 liczba odwrotna to 23..., a wiec: 23X = 4 mod 48 // 23 X = 4*23 mod 48 X = 92 mod 48 X = 92 − podloga(92/48)*48 = 92 − 48*1 = 44

asdf: czyli: X = 48k + 44, k ∊ Z

Saizou : 23x=4 mod48 −25x=100 mod48 x=−4 czyli x=−4+48t ,t∊ℤ

asdf: czemu 100?

Saizou : zmieniłem tylko reprezentanta, bo relacje modulo jest dobrze określona

asdf: racja, dzieki, masz jeszcze?

Saizou : ale nie skończyłeś

asdf: eh...y jeszcze 23*44 + 48*y = 4 48y = 4 − 23*44

	4−23*44
y =
	48

...też liczba

Saizou : wyprowadź cechę podzielności przez 11

Saizou : skoro x=−4+48t to jakim cudem y jest liczbą ?

asdf: zamienilem to do postaci: 23X + 48y = 4 X = 48t + 44 23*44 + 48*y = 4 23*(48t + 44) + 48y = 4

	23(48t + 44)
y =
	48

asdf: od czego zaczac wyprowadzanie cechy podzielnosci przez 11?

Saizou : tylko t pożarłeś rozpatrz liczę w postaci a=a_o+a₁10+a₂10ⁿ+...+a_n10ⁿ

Saizou : tam przy a₂10²

zombi: Daj mu coś cięższego

Saizou : zombii jbc to pamiętam o zadanka od Ciebie

zombi: Spoko, mogę wrzucić później jeszcze jakieś

Saizou : trzeba stopniowo wprowadzać, żeby nie zniechęcić

asdf: suma cyfr musi byc parzysta

asdf: zombi, nie kazdy jest na studiach matematycznych, inni sa, np. na informatyce..pokrewne, ale nie poswiecam dni na matematyke, tylko, np. na programowanie

Saizou : ale nie pokazałeś tego

asdf: nie mam pomyslu na to

zombi: Spoko adsf rozumiem to

Saizou : a co powiesz o takiej kongruencji 10≡10 mod11 10≡−1 mod11 10^k≡(−1)^k mod11

asdf: czyli: 10 mod 11 + 100 mod 11 = 1 −1 = 0 10 mod 11 + 100 mod 11 + 1000 mod 11 = 1 − 1 + 1 = 1 dobry trop?

asdf: znaki pomylilem

Saizou : kombinujesz dobrze, tylko to uogólnij xd

asdf: pomnozylem sobie troche i mi wyszlo, ze suma na (nieparzystych mod 11) − (suma na parzystych mod 11) = 0

Saizou : i jest ok ale dla formalizmu a₀+a₁10+...+a_n10ⁿ≡a₀−a₁+a₂−a₃+....+(−1)ⁿa_n mod11 i wyciągnąć wniosek

asdf: czyli ∑_i=0ⁿ(−1)ⁱa_i = 0 ?

asdf: czytelniej: _i=0∑ⁿ (−1)ⁱa_i = 0

zombi: raczej ∑(−1)ⁱa₀ ≡ 0 mod 11

zombi: ∑(−1)ⁱa_i **

asdf: a, no tak: ∑(−1)ⁱa_i ≡ 0 mod 11

asdf: czyli: 11 | ∑(−1)ⁱ a_i

asdf: macie cos jeszcze?

Saizou: asdf wyluzuj troche, dzisiaj juz baluj

asdf: siedze tak od 19 do 00:30...ale ja tak moge cale dnie siedziec i cos robic

Saizou: to uzasadnij WTF , a tak na serio zbastuj i sie ciesz ostatnim dniem w roku, w koncu tylko jeden taki jest

asdf: jeszcze znalazlem zadanko z podzielnoscia przez 37, to bedzie tak? : a = a₀ + a₁*10¹ + ... + a_n*10ⁿ 1*10⁰ ≡ 1 mod 37 1*10¹ ≡ 10 mod 37 1*10² ≡ 26 mod 37 jesli tab = [ 1, 10,26 ], indeksujemy od 0, to: 1*10ⁱ ≡ tab[i mod 3] mod 37, np. i = 4, to 4 mod 3 = 1, a wiec tab[1] = 10 to jesli: a wiec dla: a_i * tab[i mod 3 ] = c_i jesli: 37 | ∑ a_i*tab[i mod 3] to jest liczba podzielna przez 37?

asdf: tam powinno byc: to jesli: np. i = 5, to : i mod 3 = 2, tab[2] = 26 a₅* 26 itd...

asdf: ok, dziala − nie wiem jak to sie matematycznie zapisuje, ale zaprogramowac moge To jak nie chcecie mi pomoc to ide robic taski z pracy Dzieki wielkie, cześć!