s euklides: Mam znaleźć takie liczby x i y, żę: 252x + 198y = NWD(252,198) 252x + 198y = 18 / :18 14x + 11y = 1 14x + 11y = 1 14 = 3 * 3 + 2 3 = 2 * 1 + 1 1 = 3 − 2 * 1 = 3 − 11 + 3 * 3 = 4 * 3 − 11 = 4*(14 − 11) − 11 = 4 * 14 − 4 * 11 − 1 = 4 * 14 − 5 * 11 Mam rozwiązanie, ale nie mogę tego zrozumieć skąd np. jest v ? Wiem,że to z algorytmu euklidesa ale nie mogę tego zrozumieć.

euklides: pomoże ktoś ?

Saizou : 14x+11y=1 ⇒14x≡1 mod11⇒3x≡1 mod11⇒12x≡4 mod11⇒x≡4 czyli każda liczba w postaci x=11k+4 14(11k+4)+11y=1 154k+56+11y=1 11y=−154k−55 y=−14k−5 dla k∊ℤ np. dla k=0 mamy x=4, y=−5

euklides: rozumiem do linijki 3x≡1 mod 11, ale skąd potem 12x?

euklides: saizou a czy skorzystałeś z algorytmu euklidesa tutaj?

Saizou : nie, nie korzystałem z algorytmu bezpośrednio 14x≡1 mod11 3x≡1 mod11 /*4 (kongruencje możemy mnożyć przez liczby całkowite stronami) 12x≡4 mod11⇒x≡4

ziom: a na algorytm euklidesa byłbyś w stanie przetłumaczyć ?

Saizou : policzmy NWD(14,11) za pomocą AE 14=11*1+3 →3=14−11*1 11=3*3+2 →2=11−3*3 3=2*1+1 →1=3−2*1 2=1*2+0 NWD(14,11)=0 i teraz zapisujemy to tak jakby od końca 1=3−2*1 (i wstawiamy za 2=11−3*3) 1=3−(11−3*3)=3−11+3*3=4*3−11 wstawiamy (3=14−11) 1=4(14−11)−11=4*14−5*11 zatem x=4 y=−5

ziom: ok dzięki już ogarniam powoli, w razie co będę pisać.

euklides: mam jeszcze jedno zadanie tego typu które sam zrobiłem, ale nie wiem czy dobrze: 221x + 754y = NWD(221,754) 221x + 754y = 13 / :13 17x + 58y = 1 58 = 17 * 3 + 7 −> 7 = 58 − 17 * 3 17 = 7 * 2 + 3 −> 3 = 17 − 7 * 2 7 = 3 * 2 + 1 −> 1 = 7 − 3 * 2 1 = 7 − 3 * 2 = 7 − (17 − 7 * 2) * 2 = 7 − 2 * 17 + 7 * 3 = 7 * 4 − 2 * 17 = (58 − 17 * 3) * 4 − 2 * 17 = 58 * 4 − 17 * 3 * 4 − 2 * 17 = 58 * 4 − 17 * 12 − 2 * 17 = 58*4 − 17 * 14 i nie wiem czy to dobrze ? bo niby powinnien być znak + przed liczbą 17

Saizou : 17x+58y=1 to jest tak jakby ogólna postać ale 58y−(−x)17=17x+58y

euklides: to dobrze zrobiłem? x = −14 , y = 4 ?