MD 1551: Znaczenie zapisu matematyka dyskretna. Co oznacza zapis : 255x≡₅₂₇134 I w jaki sposób rozwiązać to zadanie. Dodam, że trzeba wykorzystać rozszerzony algorytm Euklidesa, ale nie mam zielonego pojęcia do czego służy nam w tym zapisie liczba 134. Bo liczymy to z NWD(527,255) i otrzymujemy wynik 17. Ale w jakim celu jest podana liczba 134?

Adamm: to jest przystawanie modulo 527, czyli 527|255x−134 żeby to zachodziło to musi być 17|255x−134 czyli 17|134 co nie zachodzi równanie nie ma rozwiązań

1551: A mógłbyś zrobić jakiś przykład gdzie to zachodzi i objaśnić co i jak ?

Adamm: 255x≡₅₂₇136 ponieważ 17|255x−136 to możemy 527, 255 oraz 136 podzielić przez 17 15x≡₃₁8 31=2*15+1 −2*15+31=1 −16*15+8*31=8 mamy nasz x, −16 więc wynik to x=−16+31k gdzie k∊ℤ

1551: Dziękuję. Miłej niedzieli.

Adamm: mam nadzieję że będzie miła dziękuję i nawzajem

1551: Nie rozumiem tylko zapisu : 31=2*15+1 // tutaj korzystamy NWD(31,15), dobrze rozumiem ? −2*15+31=1 // otrzymujemy 1=31+15(−2) −16*15+8*31=8 // i tutaj nie wiem skąd się bierze ten zapis, a tym samym nie skąd liczmy x.

Adamm: 1. z algorytmu Euklidesa 2. przekształcony wzór 3. mnożymy razy 8, bo tak mamy w równaniu 15x=₃₁8 31 jest zawsze podzielne przez 31, więc możemy to zignorować możesz to potraktować jako −16*15=₃₁8

1551: Za moment wrzucę drugi przykład rozwiązany przeze mnie, byłbym wdzięczny gdybyś jeszcze mógł go sprawdzić.

1551: http://imgur.com/Y9sxNlW Tutaj rozwiązany inny przykład, tylko nie wiedziałem co zrobić gdy NWD wyszło 1, czyli liczby względnie pierwsze, dzielenie równanie przez 1 nie ma sensu bo niczego nie zmieni.

1551: Tutaj poprawka : http://imgur.com/1kM4ytY

Adamm: algorytm Euklidesa jest dobry dalej jest bez sensu wyznaczasz 1=15*a+499*b robisz to idąc w wstecz wraz z algorytmem Euklidesa 11*a to będzie twój x w równaniu

Adamm: oczywiście może różnić się o 499k gdzie k jest liczbą całkowitą

1551: No właśnie jakoś nie mogę tego zrozumieć co, jak i kiedy No nic, zaraz jeszcze popróbuję i będę się odzywał w tym temacie.

Adamm: 1=4−3 ale 3=15−4*3 1=4*4−15 ale 4=499−15*33 1=4*499−133*15 mamy nasz a=−133 oraz b=4 b jest nam w niczym nie potrzebne x=−133*11+499k=34+499k gdzie k∊ℤ (tutaj dodałem parę 499 by uprościć wynik)

1551: Aha, czyli korzystamy tutaj z rozszerzonego algorytmu Euklidesa i doprowadzamy do postaci linearnej równania. Już rozumiem, tylko jeszcze jedyną wątpliwość mam − co do x. Dlaczego nie korzystamy z b=4 − i czy zawsze je pomijamy ? A czy zostawienie zapisu x=−133*11 byłoby poprawne czy należy dodać x=−133*11+499k ?

Adamm: x=−133*11 to jedynie jedno rozwiązanie zazwyczaj celujemy we wszystkie b pomijamy ponieważ "ginie" przy kongruencjach 4*499=₄₉₉0 jeśli więc mamy równanie z przystawaniem modulo n, to przy algorytmie Euklidesa zawsze możemy pominąć współczynnik przy n, po przy przystawaniu właśnie jak powiedziałem wcześniej, "ginie"

Adamm: nie chodzi mi o to by pomijać je w trakcie obliczeń, tylko na końcu oczywiście

1551: Czyli prawidłowe rozwiązanie powinno wyglądać tak : http://imgur.com/6HVZC76 ? Czy dobrze to zrozumiałem ?

Adamm: x=133*11 jest rozwiązaniem ale chcieliśmy uzyskać wszystkie możliwe rozwiązania całkowite

Adamm: x=−133*11

1551: Czyli rozwiązaniem jest x=−133*11 ? Ale, aby uzyskać wszystkie możliwe rozwiązania dodajemy 499*k gdzie k∊Z ? A więc "ogólne/rozszerzone" rozwiązanie będzie równe x=−133*11 + 499k, racja ?

Adamm: tak

1551: Dzięki wielkie, bardzo pomogłeś.