teoria liczb maniek: mógłby ktoś pomóc w nauczeniu się kongruencji ? a) 6x = 3 mod 9 b) 2000x = 3 mod 643

Vax: Jasne, generalnie trzeba tutaj wiedzieć, że kongruencja liniowa ax = b (mod c) ma rozwiązanie wtedy i tylko wtedy, gdy nwd(a,c) | b. Dodatkowo, jeżeli masz kongruencje ax = b (mod c) i istnieje takie n, że n | a,b,c, to nasza kongruencja jest równoważna (a/n)x = b/n (mod c/n). Łatwo to się uzasadnia, jeżeli a = na' , b = nb' , c = nc', to mamy równoważnie n(a'x−b') = 0 (mod c'n) a to jest równoważne a'x−b' = 0 (mod c') ⇔ a'x = b' (mod c'). Czyli np mając 6x = 3 mod 9 jest to równoważne 2x = 1 mod 3 /*2 ⇔ 4x = 2 mod 3 ⇔ x = 2 mod 3. Dodatkowo jeżeli (a,b) = 1, to istnieje element odwrotny do a mod b (zapisuje się to po prostu a⁻¹ mod b), czyli taka liczba k, że a*k = 1 mod b, wyznaczamy go przy pomocy rozszerzonego algorytmu Euklidesa. No to np tą 2 kongruencje rozwiązujemy tak, że: 2000 = 71 mod 643, więc 2000x = 3 mod 643 ⇔ 71x = 3 mod 643, z rozszerzonego algorytmu Euklidesa wyznaczamy, że 71⁻¹ = 480 mod 643, więc 71x = 3 mod 643 /*480 ⇔ x = 154 mod 643. Jakbyś miał jeszcze jakieś pytania pisz

maniek: 1) 2x = 1 mod 3 / * 2 ⇔ 4x = 2 mod 3 po co mnożymy tutaj przez dwa? i dlaczego to jest równoważne x = 2mod 3 ?

maniek: 2) 2000 = 71 mod 643, więc 2000x = 3 mod 643 skąd ta trójka? oraz wyżej napisałeś "dodatkowo (a, b) = 1" − co to oznacza?

Vax: Mamy 2x = 1 mod 3 i chcemy przemnożyć przez taką liczbę, żeby przy x stała 1, (czyli przez element odwrotny do 2 mod 3). Zauważ, że 2*2 = 4 = 1 mod 3, czyli mnożąc przez x dostajemy 4x = x mod 3, więc 2x = 1 mod 3/*2 ⇔ 4x = 2 mod 3 ⇔ x = 2 mod 3

Vax: Tą trójkę masz podaną w przykładzie, a (a,b) to skrót od nwd(a,b).

maniek: no ok, a skąd bierze się to 71 ? tj.: 2000x = 2 mod 643 ⇔ 71x = 3 mod 643 ?

Vax: Bo 2000 = 71 mod 643 więc mnożąc przez x dostajesz 2000x = 71x mod 643.

maniek: ok to chyba rozumiem dziękuje a jak rozwiązać taki układ ? :

⎧	2x = 1 mod 3
⎨	3x = 1 mod 4
⎩	5x = 4 mod 7

Vax: Każdą z kongruencji mnożymy przez taką liczbę, aby przy x dostać 1, czyli: {2x =1 mod 3/*2 {3x = 1 mod 4/*3 {5x = 4 mod 7/*3 ⇔ {x = 2 mod 3 {x = 3 mod 4 {x = 5 mod 7 Z pierwszej kongruencji wynika, że x = 3t + 2 dla dowolnego całkowitego t, wstawiamy to do 2 kongruencji: 3t+2 = 3 mod 4/−2 ⇔ 3t = 1 mod 4/*3 ⇔ t = 3 mod 4 A to oznacza, że t = 4k+3 dla dowolnego całkowitego k, więc x = 3t+2 = 3(4k+3)+2 = 12k+11, wstawiamy to do ostatniej kongruencji: 12k+11 = 5 mod 7/−11 ⇔ 12k = −6 mod 7, ale −6 = 1 mod 7 oraz 12k = 5k mod 7, więc jest to równoważne 5k = 1 mod 7/*3 ⇔ k = 3 mod 7 czyli k = 7n+3 dla dowolnego całkowitego n, ostatecznie rozwiązaniem jest x = 12k+11 = 12(7n+3)+11 = 84n+47 dla dowolnego całkowitego n.

maniek: 1 i 2 rozumiem natomiast 5x = 4 mod 7 /* 3 dlaczego x = 5 mod 7, skąd ta piątka?

maniek: 12 mod 7 = 5 mod 7 teraz rozumiem

Vax: Tak I przy okazji nie trzeba przy każdej liczbie pisać mod coś, wystarczy dodać to na końcu, tj u nas 12 = 5 mod 7, przy dłuższych przykładach mocno skraca to zapis, bo znak równości możemy pisać wielokrotnie

maniek: to mam jeszcze jedno zadanie: Mając dane a, b ∊ ℤ oraz m, n ∊ N⁺ podaj warunek konieczny, aby układ

⎧	x = a mod m
⎩	x = b mod n

miał rozwiązanie.

Vax: Z 1 równania mamy x = mk+a dla dowolnego k ∊ ℤ, więc wstawiając do 2 dostajemy mk+a = b mod n ⇔ m*k = b−a mod n a to jak wiemy ma rozwiązanie wtedy i tylko wtedy, gdy nwd(m,n) | b−a (pisałem w 1 poście, że kongruencja ax = b mod c ma rozwiązanie wtedy i tylko wtedy, gdy nwd(a,c) | b) Przy okazji widzimy, że jest to warunek konieczny i wystarczający, tj mamy relację równoważności tutaj

maniek: czemu nie mogłem na to wpaść od początku dziękuję ci bardzo za pomoc, dobranoc

Vax: Dobranoc.

maniek: to jeszcze tak dla bezpieczeństwa zapytam, dlaczego w tym układzie

⎧	2x = 1 mod 3/*2
⎨	3x = 1 mod 4/*3
⎩	5x = 4 mod 7/*3

mnożymy przez 2, 3, 3, wolę upewnić się czy dobrze myślę

Vax: Chcemy przy każdej kongruencji przy x mieć współczynnik 1, przy małych ,,mod" możemy na palcach sprawdzić przez co trzeba przemnożyć daną kongruencję, aby dostać 1, np mając 5x = 4 mod 7, jeżeli przemnożylibyśmy przez 2 dostalibyśmy 10x = 8 mod 7 czyli 3x = 1 mod 7, czyli mamy 3, a chcemy mieć 1, sprawdzamy czy zadziała jak przemnożymy przez 3, istotnie wtedy mamy 15x = 12 mod 7 czyli x = 5 mod 7. Dla większych modulo oczywiście nie sprawdzamy tego na palcach bo to bez sensu, stosujemy rozszerzony algorytm Euklidesa, który ma logarytmiczną złożoność, więc jest ,,dość" szybki

maniek: nie widzę jak otrzymujemy tą 1 i jak to sprawdzasz 10x = 8 mod 7 czyli 3x = 1 mod 7, dlaczego otrzymujemy 3? 8 mod 7 = 1, skad ta trójka ?

maniek: można liczyć na odpowiedź? dlaczego one są równe?

maniek: najlepszym pomysłem jest chyba zrobienie jednego całego przykładu a) 3x + 2 = 1 mod 5 3x = −1 mod 5 i teraz tak jak pisałeś muszę pomnożyć przez element odwrotny, czyli 3⁻¹ mod 5, ale ile to będzie wynosiło ?

Vax: 3{−1 = 2 mod 5, bo 3*2 = 1 mod 5, więc 3x = −1 mod 5 /*2 ⇔ x = −2 = 3 mod 5 A to 10x = 8 mod 7 ⇔ 3x = 1 mod 7 wynika stąd, że 10x = 3x mod 7 oraz 8 =1 mod 7.

maniek: 3{−1 = 2 mod 5 ? co to ma dokładnie oznaczać ?

Vax: Przez a⁻¹ mod b oznaczamy taką wartość t, że a*t = 1 mod b, czyli 3⁻¹ mod 5 to taka liczba x, że 3x = 1 mod 5, jak łatwo sprawdzić x = 2 mod 5.

maniek: przepraszam Cię, ale jeszcze nic z tego nie rozumiem 3x + 2 = 1 mod 5 3x = −1 mod 5 i mógłyś teraz w krokach napisać co należy po kolei zrobić? jak wyznacza się to a⁻¹ od początku do końca, jakiś schemat na to jest? bo nic nie widzę

Vax: Jak pisałem, przy małych modulo najszybciej liczyć na palcach, chcemy znaleźć taką liczbę, aby mnożąc 3 przez nią dostać 1 mod 5. Sprawdzamy czy jest nią 1: 3 * 1 = 3, to jest różne od 1 mod 5, sprawdzamy 2: 3*2 = 6, ale 6 = 1 mod 5, czyli elementem odwrotnym do 3 mod 5 jest 2, więc mając: 3x = −1 mod 5 mnożymy obie strony przez 2 i dostajemy: x = −2 mod 5 Ale −2 = 3 mod 5, więc: x = 3 mod 5 i takie jest rozwiązanie.

maniek: pierwsze pytanie wejściowa postać to 3x + 2 = 1 mod 5 przkeształcona na 3x = −1 mod 5 dlaczego w swoim rozwiązaniu napisałeś "3 przez nią dostać 1 mod 5" ? drugie pytanie jezeli to jest prawdziwe to chodzi o to ze podstawiamy kolejne liczby i sprawdzamy rownanie? a) 1 : 3 * 1 = 1 mod 5 , nie b) 2: 3 * 2 = 1 mod 5, 5 * 1 + 1 = 6, czyli się chyba zgadza o to chodzi? trzecie pytanie dlaczego mnożymy przez 2, czyli jeżeli mamy liczbę 3 * 2, to 3 jest a, a dwójka to a⁻¹ ? czwarte pytanie dlaczego po przemnożeniu przez 2 dostaliśmy x = −2 mod 5 ?, dlaczego znikneła trójka? piąte pytanie czy rozwiązaniem nie jest już x = −2 mod 5? i jak to przeksztalcic na liczbę x = 3 mod 5, dlaczego to jest równe ? przepraszam za ten nawał pytań ale bardzo mi na tym zależy

Vax: 1) nie rozumiem pytania 2) tak 3) Tak, mając jakiś element a (u nas a=3) przez a⁻¹ mod b, oznaczamy taką liczbę, że a * a⁻¹ = 1 mod b (u nas a⁻¹=2) 4) Mamy 3x = −1 mod 5. Mnożąc obustronnie przez 2 dostajemy 6x = −2 mod 5, ale 6x = x (mod 5) (widzisz czemu ? Po odjęciu obustronnie x jest to równoważne 5x = 0 (mod 5) co jest prawdą, bo dla dowolnego całkowitego x zachodzi 5 | 5x), oraz −2 = 3 mod 5, gdyż jest to równoważne (po dodaniu obustronnie 2) 0 = 5 mod 5, co jest prawdą, bo 5 | 5, więc skoro mamy 6x = −2 mod 5, oraz wiemy, że 6x = x mod 5 oraz −2 = 3 mod 5 możemy napisać x = 3 mod 5. 5) Na to odpowiedziałem wyżej

maniek: rozumiem z ostatniego postu prawie wszystko prócz: "więc skoro mamy 6x = −2 mod 5, oraz wiemy, że 6x = x mod 5 oraz −2 = 3 mod 5 możemy napisać x = 3 mod 5."

Vax: Po prostu jeżeli mamy a = b mod c, to możemy to równoważnie zapisać (a mod c) = b mod c, tak samo a = (b mod c) mod c, albo (a mod c) = (b mod c) mod c, czyli konkretnie mówiąc możemy manipulować lewą, lub prawą lub obiema stronami dodając/odejmując wielokrotności c, czyli mając 6x mod 5, możemy to zapisać jako x mod 5, bo 5x jakby nie patrzeć jest wielokrotnością 5, więc 6x = 6x − 5x = x mod 5

Vax: A tymczasem idę już spać, jakbyś miał jeszcze jakieś pytania/wątpliwości pisz, później postaram się odpisać.

maniek: chyba z tym ostatnim punktem musze się przespać, to wracając do początkowego przykładu: a) 6x = 3 mod 9 2x = 1 mod 3 tak jak napisałeś podstawiam po kolei: dla x = 2 jest 3 * 1 + 1 = 4 2x = 1 mod 3 / * 2 x = 2 mod 3 czy mogę automatycznie pisać już tę równość przy mnożeniu?

maniek: dziękuję za pomoc i jakbyś mógł poźniej odpisać na powyższe pytanie

Vax: Tak, możesz automatycznie z 2x=1 mod 3 przechodzić do x = 2 mod 3.

maniek: ok dziękuję, a taki przykład: 5x = 2 mod 11 7: 3 * 11 + 2 = 35 = 5 * 7 5x = 2 mod 11 /* 7 x = 14 mod 11 i to jest ostateczna odpowiedź ?

Vax: Nie, przecież 5*7 = 35 = 2 mod 11, a my chcemy mieć 1. Zauważ, że 5*9 = 45 = 1 mod 11, więc należy nasze równanie przemnożyć przez 9: 5x = 2 mod 11/*9 45x = 18 mod 11 x = 7 mod 11

maniek: ale jak to chcemy mieć jeden? 5 * 7 = 3 * 11 + 2 5 * 9 = 4 * 11 + 1 to tak spełnia, czyli musze zawsze rozwiązywać dla ax = 1 mod b, tak? i to co otrzymamy przemnażamy przez ta cala liczbe 45x = 18 mod 11 − to jeszcze rozumiem x = 7 mod 11 − to skąd ? jest chyba inne niz przyklady wyzej

Vax: Kolejno: Pierwszy krok, zauważamy, że: 45 = 1 mod 11 Drugi: Mnożymy 45=1 mod 11 obustronnie przez x i dostajemy: 45x = x mod 11 Mamy równość 45x = 18 mod 11 Ale wiemy, że 45x = x mod 11 Więc możemy w równości 45x = 18 mod 11 wartość 45x zastąpić przez x, bo 45x = x mod 11 Więc x = 18 mod 11 Ale 18 = 7 mod 11 Więc możemy równości x = 18 mod 11 wartość 18 zastąpić przez 7: x = 7 mod 11 Widzisz już o co chodzi?

maniek: chyba już tak , w końcu, dziekuje w układzie równań z 29 lipc 03:10, tak samo? rozwiazujemy ax = 1 mod b, dla kazdego przypadku? a) 2 * 2 = 4 = 3 * 1 + 1 = 1 mod 3 b) 3 * 3 = 9 = 4 * 2 + 1 = 1 mod 4 c) 3 * 5 = 15 = 7 * 2 + 1 = 1 mod 7 o to chodziło ?

Vax: Tak jest, dlatego w tamtym układzie mnożymy te równania przez 2,3,3, żeby we wszystkich 3 kongruencjach przy x mieć 1

maniek: to został tylko do zrozumienia ten przykład b) 2000x = 3 mod 643 czy go da się zrobić tak jak wyżej opisałeś te kroki?

maniek: