Znaleźć wszystkie liczby całkowite Nowbie : Zadanie 1. Znaleźć wszystkie liczby całkowite, które przy dzieleniu przez 6 dają resztę 4,a przy dzieleniu przez 11 dają resztę 8. Jaką dają te liczby resztę, przy dzieleniu przez 66? Zadanie 2. Znaleźć wszystkie liczby całkowite, które przy dzieleniu przez 7 dają resztę 5,a przy dzieleniu przez 4 dają resztę 3. Właściwie, to oba są podobe, prosiłbym o wytłumaczenie na przykładzie 1. Moje wypociny: x=6k+4 x=11t+8 6k+4=11t+8 6k−11t=4 NWD(6,−11) = 1 −11 = −1*6−5 6=−1*(−5)+1 −5=−5*1+0 1=6+1*(−5)= 6+1*(−11+1*6)=6+1*(−11)+1*6=1*(−11)+2*6 t0=1 k0=2 I już tutaj mi się nie zgadza − po podstawieniu do góry, lewa ≠ prawej Możliwe, że to jest całkowicie zły sposób. Nie miałem jeszcze indukcji (i nie mogę jej użyć). Proszę o pomoc W ZROZUMIENIU.

Nowbie :

Vax: 1) { x = 4(mod 6) /*11 { x = 8(mod 11) /*6 { 11x = 44 (mod 66) −{ 6x = 48 (mod 66) 5x = −4 (mod 66) /*13 −x = −52 (mod 66) x = 52(mod 66) 2 przykład analogicznie.

Nowbie : znak "=" jest znakiem równości czy przystawania? Dlaczego w pierwsze pomnożyłeś przez 11, a drugie przez 6? Nic z tym modulo nie rozumiem

Vax: Tak, przystawania. A pomnożyłem tak, żeby dostać w obu kongruencjach te same mod, potem dodaję/odejmuje stronami i dostaje zwykłą kongruencję którą już łatwo rozwiązać.

Nowbie : Ok, to już w miarę rozumiem. A dlaczego później *13? Dlaczego 5x * 13 = −x? Tak właściwie to rozumiem, że: x = 52(mod 66) Jest wzorem na te liczby? Czy na resztę, którą otrzymam po dzieleniu przez 66?

Vax: 52 to reszta z dzielenia danych liczb przez 66, ogólnie te liczby wyrażają się wzorem x = 66t+52 , t ∊ ℤ

Nowbie : A to mnożenie przez liczbę 13?

Vax: Mamy 5x = −4 (mod 66) Czyli chcemy tą kongruencję przemnożyć przez taką liczbę, żeby przy x była 1 (mnożymy przez tzw. element odwrotny, możemy go wyznaczyć z rozszerzonego algorytmu Euklidesa), jednak tutaj zauważyłem, że 5 | 65, a 65 = −1 (mod 66), potem wystarczy przemnożyć obustronnie naszą

	65
kongruencje przez (−1), tak więc mnożę ją obustronnie przez		= 13
	5

Nowbie : Czyli w przykładzie 2) {x = 5 (mod 7) /*4 {x=3 (mod 4) /*7 −{4x = 20 (mod 28) {7x = 21 (mod 28) 3x = 1 (mod 28) /* element odwrotny? Przy rozsz. algrytmie Euklidesa jakie biorę liczby?

Vax: Tutaj masz podobną sytuację jak poprzednio, nie musisz wyznaczać elementu odwrotnego, możesz zauważyć, że 3 | 27, spróbuj pomnożyć obustronnie naszą kongruencję przez 9 i zobacz co dostaniesz

Nowbie : Hmm... 3x = 1 (mod 28) /*9 27x − 9 (mod 28) coś chyba nie tak − możesz tłumaczyć dalej? Bo robisz to dośc dobrze

Vax: 27x = 9 (mod 28) Teraz zauważ, że 27 = −1 (mod 28)

Nowbie : O kurcze... ale to skomplikowane. Nadal przy "x" mam 27 i nie wiem skąd 27 = −1 (mod 28). To zadanie może mi jutro uratować dupe...

Vax: No tak nie zawsze wyjdzie, ale staram się Ci pokazywać jak można skracać niektóre obliczenia, a co do 27 = −1 (mod 28) to to są własności kongruencji, dodaj do obu stron 1 a dostaniesz 28 = 0 (mod 28) co jest oczywiście prawdziwe

Ktos: Patrzę na te własności i nadal nie widzę tego, jak zniknęła ta 9

Newbie: 27x = 9 (mod 28) 9x = 27 (mod 28) x = 3 (mod 28) Chyba tak ta przemienność nie działa?

Vax: Ale ta 9 nigdzie nie znika, mamy: 27x = 9 (mod 28) Ale: 27 = −1 (mod 28), czyli mnożąc to przez x dostajemy 27x = −x (mod 28), czyli naszą kongruencję: 27x = 9 (mod 28) możemy zapisać, jako: −x = 9 (mod 28) Mnożąc teraz tą kongruencję przez (−1) (żeby pozbyć się przy x minusa) dostajemy: x = −9 (mod 28) No i znowu −9 = 19 (mod 28) więc: x = 19(mod 28)

Vax: No niestety, tak nie działa

Newbie: 27x = 9 (mod 28) −−> przejście z tego, do tego niżej nadal nie jest mi znane. Zniknął x i 9 ** 27 = −1 (mod 28) − gdzie teraz podział się x? **A tutaj 27x = −x (mod 28) −−> 27x = 9 (mod 28) znowu się on pojawia. Wiem, że jestem dość oporny na tą wiedzę, jeśli prościej się tłumaczyć nie da, to może już nie będę zawracał Ci głowy

Vax: Ale to nie jest tak, że z 27x = 9 (mod 28) przechodzimy do 27 = −1 (mod 28), może napiszę tak. Mamy: 27x = 9 (mod 28) ~~~~ I teraz STOP, koniec dalszych przekształceń, to co zaraz będzie na dole nie jest żadnym przekształceniem tego na górze, po prostu zwykłe luźne spostrzeżenie: 27 = −1 (mod 28) Widzimy, że coś takiego zajdzie, bo dodając obustronnie 1 jest to równoważne 28 = 0 (mod 28) co jest prawdą. I teraz patrzymy, co z tego dostajemy, wiemy, że: 27 = −1 (mod 28), więc mnożąc obustronnie przez x dostajemy: 27x = −x (mod 28) ~~~~ I dopiero teraz z powrotem wracamy do naszej kongruencji: 27x = 9 (mod 28) Ale z wniosku wyżej wiemy, że 27x = −x (mod 28) więc możemy zapisać: −x = 9 (mod 28) I dalej już dokończyłem w poprzednim poście. Mam nadzieję, że już widzisz ocb

Newbie: Teraz już wiem o wiele więcej, cały czas myślałem, że jest to przekształcenie. 27x = 9 (mod 28) −− to jest jasne 27x = −x (mod 28) −− to też jest jasne −x = 9 (mod 28) −−tutaj znowu nie wiem Chyba Ci kurierem wyślę jakąś nagrodę za tą pomoc...

Vax: Istnieje własność kongruencji, że jeżeli: a = b (mod q) a = c (mod q) To b=c (mod q), z tego właśnie korzystamy. Np: 20 = 6 (mod 7) 20 = 13 (mod 7) z tego wynika 6 = 13 (mod 7), spróbuj to przeanalizować, jakbyś miał jakieś pytania to pisz, tylko jbc odpiszę jutro, bo teraz już lecę spać

Mila: inaczej: Twoje zapisy: 1) x=6k+4 2) x=11t+8 pierwsze równanie pomnóż przez 11 a drugie przez 6 mamy: 3) 11x= 66k + 44 4) 6x = 66t + 48 po 5x odjęciu stronami 5) 5x = 66 (k−t) − 4 teraz od 4 równania odejmujesz 5 równanie i mamy x = 66(t−k − t) +52 szukana reszta to 52

Newbie: Jesteś moim mistrzem, teraz na prawdę zrozumiałem zadanie, które uważałem na najgorsze. Jak mogę się jakoś odwdzięczyć to pisz w temacie

Mila: Mam nadzieję, że ten miły komentarz to dla mnie. Kongruencję mogę wyjaśnić prosto kiedy indziej.

Newbie: To akurat do "Vax" − bo wykazał wiele cierpliwości tłumacząc mi to. Ale Tobie oczywiście też bardzo dziękuję. Jeśli będę potrzebował tłumaczenia to się odezwę