Działania modulo rączszka: 3a ≡ 2 (mod 5) czy ktoś wie, czemu z tego wynika a = 5b+4?

Vax: Tak, w takich sytuacjach rozpatrujemy po prostu wszystkie możliwości, podstawiamy 0,1,2,3,4 i zauważamy, że dla a=4 dana kongruencja jest prawdziwa, więc spełniają je wszystkie: a = 5n+4 gdzie n jest dowolną liczbą całkowitą. Pozdrawiam.

rączszka: A nie można tego po prostu tak zrobić: 3a ≡ 2 (mod 5) −> czyli 5 dzieli 3a−2

	5b+2
3a−2 jest podzielne przez 5, czyli 3a−2=5b −> a=
	3

czy to muszą być liczby całkowite raczej

Vax: Tak, to polega na wyznaczeniu liczb całkowitych spełniających daną kongruencje, tak by było za łatwo Pozdrawiam.

rączszka: Ok, dzięki

Jack: nie może być żadnego strzelania (brania wszstkich mozliwosci −duuuużo ich) Najprościej rozwiązywać to wykorzystując algorytm Euklidesa..

rączszka: No właśnie próbuję inaczej, bo jak mam np. 3a ≡ 1 (mod 5), to wiem, jak rozwiązać, ale jak mam tam 2, to już nie mogę sobie z tym poradzić

Vax: Jack, w takich przypadkach jednak najszybciej sprawdzić kilka możliwości, dużo ich nie ma.

Jack: patrząc na równanie rzadko kiedy "widać" rozwiązanie To że mając daną już odpowiedź, faktycznie sprawdzimy kilka przypadków (albo wszystkie "rodzaje") i nam się będzie zgadzało, to inna sprawa. Rozumiem, że rączszka pytał o rozwiązanie, a nie sprawdzenie... Gdyby jednak chodziło tylko o sprawdzenie, to oczywiście masz rację

Jack: rączszka, znajdź liczbę odwrotną do 3 modulo 5 korzystając z algorytmu Euklidesa.

Vax: Skoro już podajemy inne sposoby, to ja podam inny, chociaż i tak będę stał przy swoim, że przy tego typu kongruencjach warto ,,ręcznie" poszukać rozwiązania, mając kongruencje: 3x == 2 (mod 5) Wystarczy znaleźć jedno całkowite rozwiązanie równania: 3x=5y+2 ⇔ 3x−5y=2 Od razu widać, że spełnia je (x,y) = (−1 , −1) więc mamy: x == −1 (mod 5) ⇔ x == 4 (mod 5) ⇔ x = 5n+4 Pozdrawiam.

rączszka: Zawsze tak robiłam: 3a ≡ 1 (mod 5) Najpierw szukam NWD tych liczb 5:3 = 1 reszta 2 3:2 = 1 reszta 1 2:1 = 2 reszta 0 Czyli: 3=2*1+1 5=1*3+2 1=3−1*2=3−1*(5−1*3)=3−1*5+1*3=2*3−1*5 Mam nadzieję, że jest ok

Jack: zgoda, jak mamy jedno, mamy wszystkie

Jack: dobrze, czyli 2 jest odrwotne do 3 modulo 5. 1=2*3−1*5 1≡2*3 (mod 5) Stąd 3a ≡ 1 (mod 5) a≡ 2 (mod 5) ⇔ a=5n +2, gdzie n∊N

rączszka: A jakim cudem z 3a ≡ 1 (mod 5) wyszło Ci nagle a≡ 2 (mod 5) ? Pewnie to jakaś prosta zależność i nie mogę załapać

Jack: pomnożyłem obie strony przez 2

rączszka: Aha, to dlatego że 2 jest odwrotne do 3

Jack: nie inaczej

rączszka: A jeśli 3a ≡ 2 (mod 5), to można tu jakoś wykorzystać a ≡ 2 (mod 5)?

Jack: dokladnie tak samo się to robi, tyle tylko, że na końcu 2*2=4, czyli a=4 (mod5) ⇔ a=5n+4

rączszka: Nie wiem już, tutaj trzeba zapisać 2=1*5−1*3, a potem za 1 podstawić to, co się wyznaczyło wcześniej, czyli 1=2*3−1*5? Może nieodpowiednia pora, ale jakoś nie mogę tego skumać

Vax: Jack odnośnie Twojej poprzedniej wypowiedzi, ,,zgoda, jak mamy jedno, mamy wszystkie", domyślam się, że próbowałeś mi przekazać, że mając jedno rozwiązanie, nie oznacza to, że nie ma innych? Jeżeli się nie mylę, to wydaje mi się, że nie masz racji, jeżeli mamy kongruencję postaci: a*x == b (mod c) I chcemy znaleźć wszystkie rozwiązania należące do przedziału <0 ; c) gdzie c jest liczbą pierwszą, oraz a,b ∊ (0 ; c) wykażę, że dana kongruencja ma tylko jedno rozwiązanie, załóżmy nie wprost, że posiada dwa, niech to będą p oraz q, oczywiście p,q ∊ <0 ; c) wówczas musi zachodzić: {ap == b (mod c) {aq == b (mod c) odejmując stronami: a(p−q) == 0 (mod c) Skoro c jest liczbą pierwszą, oraz a∊ (0 ; c) to musi zachodzić p==q (mod c), a skoro p,q ∊(0;c) to p=q, co jest sprzeczne z tym, że p jest różne od q. Pozdrawiam.

Jack: miałem na myśli że jesli znajdziemy jedno rozwiązanie to w prostu sposób możemy wygenerować wszystkie inne. Jest tak nie tylko dla jednego równanie ale również dla układu równań. Wystarczy skorzystać z chińskiego twierdzenia − w dowodzie tego tw. konstruuje się pewien iloraz który wykorzystujemy.

Vax: Aha, to w porządku, po prostu niepotrzebnie wyczułem niezamierzaną ironię w Twoim poście Pozdrawiam.

Jack: niepotrzebnie, bo naprawdę całkowicie się z Tobą zgodziłem! Swoją drogą, podziwiam Twój upór (ambicję)