& Trivial: ICSP. Robimy macierzowy piątek, bo nie mam co robić?

ICSP: Ja mam co robić Zaraz na UMCS jadę dowiedzieć się paru rzeczy

Trivial: To nie robimy macierzowego piątku. Daleko masz?

ICSP: no jakieś 15 min autobusem Później pewnie na orlika pójdę a wieczorem zapewne na miasto. Miasta jeszcze nie jestem pewien to może wieczorem coś porobimy

Trivial: Blisko masz. Ja z domu do uczelni mam jakieś 5 godzin...

ICSP: ale wracasz codziennie czy na stancji mieszkasz?

Trivial: Taaa, wracam codziennie. Zaledwie 10 godzin na dojazdy. Dobre.

ICSP: Czemu nie

Trivial: Bo tak.

Trivial: A co będziesz się dowiadywał?

ICSP: To może powiesz gdzie studiujesz Jakie miasto?

ICSP: Chyba najbardziej mi na planie zależy

Trivial: ICSP, nie wiesz gdzie jest AGH? o.o

ICSP: To ty na AGH studiujesz? Oczywiście Kraków.

Trivial: To dla ciebie jakieś zaskoczenie?

ICSP: Nie wiedziałem

Trivial: Na UMCS miałbym sporo bliżej, ale chciałem na AGH, żeby było daleko... Z pewnych powodów.

ICSP: Lubisz jeździć po prostu Nie wnikamy

Trivial: Dobra panie ICSP. Idę zająć się czymś bardziej konstruktywnym.

ICSP: Życzę powodzenia

Trivial: Widzę, że ICSP, wróciłeś.

ICSP: ty mnie śledzisz? Za pół godziny wychodzę

Trivial: Nie śledzę, lecz właśnie wróciłem.

Vizer: Trivial Ty znasz się może na kongruencji

Trivial: Miałem to na wykładzie jakieś 15 minut − czyli tylko podstawy. Za to Vax to pewnie ekspert w tej dziedzinie.

Vax: Jaki ekspert, kiedyś trochę o tym czytałem i tyle

Vizer: Ok to nic, próbuję coś samemu zrozumieć z neta, ale to nie jest takie proste

Vax: To jak masz jakieś pytania pisz śmiało, postaramy się pomóc

Vizer: No właśnie ta zdolność przyswajania wiedzy przez Ciebie jest zdumiewająca

Vizer: To tak zapoznałem się z podstawowymi własnościami kongruencji. mam np. problem z takim przykładem: 37x=23(mod 73) Jak mam rozpocząć takie coś rozwiązywać

Trivial: To chyba może mieć wiele rozwiązań?

AC: 74x = 46 mod 73 ⇒ x = 46 mod 73

Vax: W takich przypadkach musimy wyznaczyć element odwrotny do 37 modulo 73. Element odwrotny do jakiegoś a modulo c istnieje wtedy i tylko wtedy, gdy nwd(a,c)=1, u nas nwd(37,73) = 1, więc takowy istnieje. Elementem odwrotnym do a modulo c jest takie b, że a*b = 1 (mod c). Wyznaczyć go możemy z rozszerzonego algorytmu Euklidesa, wyznaczamy element odwrotny do 37 modulo 73, piszemy takie 2 równości: {37*0 + 73*1 = 73 {37*1 + 73*0 = 37 (najlepiej na górze zawsze pisać równanie które daje większy wynik niż na dole) Teraz patrzymy ile całych 37 mieści się w 73, dostajemy, że tylko jedna cała 37 mieści się w 73 (bo już 2*37 = 74 > 73) więc od górnego równania odejmujemy dolne przemnożone przez 1 (mnożymy przez tyle, ile ,,całości" dostaliśmy) jako 1 równanie zapisujemy to dolne, a jako 2 to które dostaliśmy po odjęciu: {37*1 + 73*0 = 37 {37(0−1) + 73(1−0) = 73−37 ⇔ 37*(−1) + 73*1 = 36 Teraz tak samo, 36 mieści się w 37 tylko raz, więc dostajemy: {37*(−1) + 73*1 = 36 {37*2 + 73*(−1) = 1 I robimy tak w kółko, dopóki nie dostaniemy w którejś równości po prawej stronie 1. U nas już dostaliśmy, i naszym elementem odwrotnym jest współczynnik stojący przy 37, w naszym przypadku 2, i teraz naszą kongruencję: 37x = 23 (mod 73) Mnożymy właśnie przez ten element odwrotny (2) dostając: x = 46 (mod 73) I to by było tyle

Vizer: Ok dzięki Vax, muszę to przestudiować uważnie, jak coś to będę pytał.

Vax: Spoko, jakby coś było niejasnego to pisz, postaram się dokładniej wytłumaczyć

Trivial: Vax, czy z innych przedmiotów też jesteś takim masterem?

Vax: Niestety, z innych przedmiotów kompletnie nic nie robię, tylko matematyka i informatyka

AC: Musisz oponować jeszcze angielski, jest niezbędny w pracy naukowej na uczelni.

Trivial: AC, Ty też jesteś w wieku Vaxa?

Vizer: Nie rozumiem pewnej kwestii, jeśli dobrze zrozumiałem to naszym zadaniem w tym przykładzie było wyznaczenie b, by wykorzystać a*b=1(mod c). Wyznaczyłeś b=2. Może głupie pytanie ale czy nie mamy pomnożyć przez 2, a=37

AC: Nie, jestem starszy. Chociaż Vax przypomina mi moje stare dobre czasy gdy startowałem w olimpiadach. Zresztą udało udało mi się zostać finalistą.

Vax: Dobrze rozumiesz, tak właśnie robimy, mamy kongruencje: 37x = 23 (mod 73) I szukamy takiego ,,b" aby 37b = 1 (mod 73), w tym przypadku można bez korzystania z rozszerzonego algorytmu Euklidesa zauważyć, że b=2 działa, jednak ogólnie jak np b=317 czy coś, to zauważyć to jest ciężko, a korzystając z metody którą opisałem wyżej bardzo szybko znajdujemy nasze ,,b"

Vax: O, w takim razie AC gratuluję osiągnięć

AC: Dzięki. Tylko, że to nie była olimpiada matematyczna.

Vax: A jaka, jak można wiedzieć ?

AC: Z matematyki byłem za cienki doszedłem tylko do szczebla wojewódzkiego, a z fizyki do ogólnopolskiego co dało mi indeks.

Vizer: No i kapie to Vax.Dzięki. Jak znajdę inny przykład, na którym się zawieszę napiszę jak coś

Vax: Spoko, powodzenia w kolejnych przykładach

Vizer: Vax mam teraz zadanie 3x=59(mod 100) NWD(3,100)=1 a*b=1(mod c) Czy z algorytmu rozszerzonego Euklidesa, gdzie mam NWD(3,100) {3*0+100*1=100 {3*1+100*0=3 {99*1+3300*0=99 {3(0−33)+100(1−0)=1 {99*1+3300*0=99 {3*(−33)+100*1=1 Wyjdzie to b=−33 Przyznam się, że nie brałem nigdy rozszerzonej wersji i nie wiem czy dobrze rozwiązuje. Czyli x=59*(−33) (mod 100)

Vax: Dobrze, tylko jak mamy (jak pisałem, w 1 równaniu większa liczba, w dolnym mniejsza): {3*0 + 100*1 = 100 {3*1 + 100*0 = 3 To w kolejnej linijce przepisujemy jako 1 równanie to dolne (u nas 3*1+100*0=3) i potem dopiero to co powstało po odjęciu, tj: {3*1 + 100*0 = 3 {3*(0−33) + 100(1−0) = 1 ⇔ 3(−33) + 100(1) = 1 Pamiętaj, że nasze b bierzemy modulo coś, więc możemy dostać jakąś liczbę ujemną, czyli: b = −33 (mod 100) Ale −33 = 67 (mod 100), więc: b = 67 (mod 100) Czyli: 3x = 59 (mod 100) /*67 x = 59*67 = 53 (mod 100) Można też pracować na liczbach ujemnych, masz b = −33 (mod 100), mnożąc mamy: x = 59(−33) = −1947 = 53 (mod 100) Wynik zostaje ten sam Należy tylko pamiętać, żeby na końcu zapisać x = coś (mod 100), gdzie coś ∊ [0 ; 100)

Vizer: Ok dzięki, jak zwykle wyczerpujące wyjaśnienia, wszystko jasne

Vizer: A i pytanie jeszcze mamy: x=59*67=53(mod 100) To 53 znajdujemy mnożąc 59*67 i patrząc na wynik mnożenia ustalić taką liczbę by 100|59*67−c

Vax: 59 * 67 = 3953, rozpatrujemy to modulo 100, czyli inaczej mówiąc bierzemy resztę z dzielenia tego przez 100, czyli 2 ostatnie cyfry − 53

Vax: No i to jest równoważne temu co piszesz, szukamy takiej najmniejszej liczby naturalnej c

Mateusz: Ogolnie kongruencje modulo n okreslamy tak: m jest w relacji z m₁ <=> n dzieli m−m₁ po prostu reszta z dzielenia m przez n jest rowna reszcie z dzielenia m₁ przez n co zapisujemy po prost tak: m=m₁(modn)

Vizer: Ok dzięki za wyjaśnienia, srry, że tak męczę, ale zaciekawiło mnie to zagadnienie. Na dzisiaj już mi wystarczy, jak coś to pomęczę Was jutro