aa Hugo: Czy istnieją liczby p,q,r,s całkowite spełniające poniższe równania? Jeśli tak, wskaż co najmniej dwie pary takich liczb. a) 4191p−7161q=132 b) 5236r+6380s=55 odp: (p₀,q₀) = (−164,−96), (p₁, q₁) = (53,31), r,s należą do Z nie istnieją, Z − chyba całkowite ?no bo chyba nie zespolone opieram się o zadanka z: https://matematykaszkolna.pl/forum/381981.html a) 4191p−7161q=132 /3 1397p −2381q = 44 NWD(p,q) 1397 2389 |1 990 1397 |1 407 990 |2 176 407 |2 55 176 |3 11 55 |5 0 11 |0 2387 − 1397 *1 = 990 1397 − 990 *1 = 407 990 − 407 *2 = 176 176 − 55*3 = 11 55−11*5 = 0 po trochu obliczeń: 5*1397 − 3*2387 = 55*3 − 11 czy to jest na razie ok ?

Hugo: źle podstawilem wyszlo mi: 44 = 96*2387 − 164*1397 wiec jedna para to: 96 i −164, chodziaz w odp mamy −96 i −164 czemu? i pyttanie jak zostały wyznaczone te drugie liczby: 53 i 31, jak do tego dojsć?

Hugo: rownanie bazowe: 1397p−2387q więc racja, −164 i 96 pytanie co dalej z tym 53 i 31? miałby ktoś pomysł ?

Mila: 4191p−7161q=132 4191=3*11*127 7161=3*7*11*31 132=2²*3*11 4191p−7161q=132 /:33 127x−217y=4 NWD(127,217)=1, i 1|4 −217=−2*127+37 127=3*37+16 37=2*16+5 16=3*5+1 Teraz odwracaj algorytm.

Mila: 1=16−3*5 5=37−2*16 16=127−3*37 37=−217+2*127 ========= 1=16−3*5=16−3*(37−2*16)=−3*37+7*16=−3*37+7*(127−3*37)= =−3*37+7*127−21*37=7*127−24*37=7*127−24*(−217+2*127)= =7*127−24*(−217)−48*127= =127*(−41)−217*(−24) ============== 127*(−41)−217*(−24)=1 /*4 127*(−164)−217*(−96)=4 x₀=−164, y₀=−96 Ogólne rozwiązanie: x=−164+217k y=−96+127k, k∊Z (Z− zbiór liczb całkowitych) k=1 x₁=−164+217=53 y₁=−96+127=31 ============

Hugo: nobel za rozwiązanie jutro Hugo ma kolokwium po południu, będe siedzieć do późna

Mila:

Hugo: pokazywałaś mi z tym x₁ = ... i y₁ ale zapomniałem wrrr zad2) Rozwiąż następujący układ kongruencji {17x−19y≡₅₉18 {23x+28y≡₅₉37 NWW(17,23) zeby oddjąc stronami 17*23 = 391 391x − 437y≡₅₉414 391x + 476y≡₅₉ 629 913y ≡₅₉215 // i modulujemy (913−15*59)y≡₅₉ (215−3*59) 28y ≡₅₉38 / :2 14y ≡₅₉19 ....

Hugo: 59 118 177 236 295 354 413 472 531 590 649 708 767 826 / 14 = 59

Hugo: odp: x= ₅₉41, y =₅₉14 885 944 1003 1062 1121 1180 1239 1298 1357 1358 = 14*97 14y ≡₅₉19/*97 14*97y − 59*23 ≡₅₉1843 y ≡₅₉1843 y ≡₅₉1843 y = 14 !

Hugo: 17x+19*14 ≡₅₉18 17x≡₅₉ −248 17x ≡₅₉ 47 119 = 7 *17 8*17 − 59*2 ≡₅₉ 47 *8 x ≡₅₉ 22 cos nie wyszło

Mila: w Z₅9 1) 17x−19y≡18 /*28 23x+28y≡37 /*19 476x−532y=504 437x+532y=703 ============= dodajemy stronami 2) 913x=1207 1207=20*59+27≡27 913=15*59+28 28x≡27 /*2 56x≡54 −3x≡−5 \*(−1) 3x≡5 3) Szukamy odwrotnej do 3 ( mamy otrzymać wynik: 59+1) 3*17=51, 3*18=54,3*19=57, 3*20=60=1(mod59) 3x≡5 /20 1x≡100 1x≡41 4) 17*41−19y≡18 697−19y=18 48−19y=18 /−18 30−19y=0 19y=30 5) odwrotna do 19 w Z₅₉ 59=3*19+2 19=9*2+1 ======= 1=19−9*2 2=59−3*19 1=19−9*2=19−9*(59−3*19)=19−9*59+27*19=−9*59+28*59 19⁻¹ to 28 w Z₅₉ 19y≡30 /28 1y≡840 y≡14 x=41,y=14 sprawdź

Mila: źle zapisałam: 1=19−9*2=19−9*(59−3*19)=19−9*59+27*19=−9*59+28*19

Hugo: dziękuję, nie śpisz , uciekasz pewnie za niedługo

Hugo: ja zacząłem od y i coś nie wyszło z x potem

Hugo: obliczasz: 19y=30 więc szukamy by został nam 1y 19*28 = 532 59 * 9 = 531 532−531 = 1 mnożymy obustronnie przez 28 19y=30 /*28 19*28y = 840 (19*28−59*9)y = 840 y = 14 wyszło

Mila: II sposób 17x−19y≡18 /*28 23x+28y≡37 /*19 476x−532y=504 437x+532y=703 Zmniejszamy wsp. 476=4*59+4 532=9*59+1, 504=8*59+32 437=7*59+24, 703=11*59+54 −−−−−−−−−−−−−−−−−−− teraz mamy układ 4x−1y=32 24x+1y=54⇔24x+1y=−5 28x=27 /*19 1x=27*19 1x=513 x≡41 y=4x−32=4*41−32=132 y≡14

Hugo: ale jak liczyłem od y to nie chciało wyjśc, pewnie gdzies popełniłem błąd y = 14 podstawiam do: 17x−19y≡₅₉18 17x − 19*14 = ≡₅₉18 / +19*14 17x = 284 7*17 = 119 59*2 = 118 7*17 − 59*2 = 1 17x = 284/ *7 x = 1988 x = 41 o kurczaki wyszło Hugo musi powoli na kolokwium rozwiązywać

Hugo: dziękuję mam nadzieje ze moja metoda tez jest Ok, Kurka wodna 2 z 9 zadań to było dopiero ; p z przykładowego kolokwium

Mila: Dobranoc

Hugo: Oblicz: a) fi(868175) b) 23 ₈₆₈₁₇₅ mod72 a) 868175 = 5*5*7*11*11*41 fi(p^k) = (p⁴(1−1/p) fi(5²*7*11²*41) = 5²(1−5)*6*11²(1−1/11)*40 = 25*4/5*6*121*10/11*40 = 528000

Hugo: dobranoc !

Hugo: 23 ₈₆₈₁₇₅ mod72 z poprzedniego zadanka fi(868175) = 528000 23 ⁽528000⁾ ≡868175 z 1 23 ⁽528000⁾ * 23 ⁽340175⁾ mod72, odp w kluczu to 47, nie wiem jak rozbić to 340175 sensownie 4)rsa, klucz prywatny (217,7) znajdź klucz publiczny n =217 , d=7 p*q = 217 = 7*31 fi(pq) = 6*30 = 180 d * e*(mod fi(*n)) = 1 7 e*(mod 180) = 1 7*103 (mod180) = 1 e = 103 M = C^d(mod n) M = 207⁷(mod 180) google nie daje rady 207⁷, na kartce sobie podaruje

Adamm: masz obliczyć 23⁸⁶⁸¹⁷⁵ mod 72 ?

Hugo: true, ale to przykladowe kolokwium próbne, w realu ma być łatwiej podobno, to studia II stopnia, nie ma przelewek

Hugo: @Adamm pomógłbyś mi z rekurencją ?

Hugo: 5,6)Rozwiąż zależność rekurencyjną.... 7)Ile ciągów ternarnych (tj. złożonych z cyfr 0, 1 i 2) spełnia tę własność, że po żadnej jedynce nie występuje ani 2 ani 0? Wyprowadź odpowiednie równanie rekurencyjne z warunkami początkowymi i rozwiąż je. 8) le jest różnych liczb pięciocyfrowych niepodzielnych przezżadną z liczb 6, 21i 35? 9) Ile jest różnych sześciocyfrowych liczb zapisanych w systemie osiemnastkowym takich, że:a)wszystkie cyfry są różne i liczba jest parzysta,b)cyfry są różne i suma cyfr trzeciej i czwartej jest równa dwanaście? Hugo jak to zrobi to by mógł iść spac czy mógłbys mi z ktorymś pomóc?

Adamm: Twierdzenie Eulera φ(72) = 24 868175 ≡ 23 (mod 24) 23⁸⁶⁸¹⁷⁵ ≡ 23⁻¹ (mod 72) 23⁻¹ trzeba tutaj taktować jako element odwrotny do 23 w ciele Z₇₂ Algorytm Euklidesa 72 = 23*3+3 23 = 7*3+2 3 = 2+1 1 = 3−2 = 3−(23−7*3) = 8*3−23 = 8*(72−23*3)−23 = ...*72−25*23 skąd 23⁻¹ = −25 = 47 w Z₇₂ Wynik: 23⁸⁶⁸¹⁷⁵ ≡ 47 (mod 72)

Hugo: 5) s_n+1 = −14s_n −49s_n−1, s₀ =−1, s₁ = −14 r² = −14r −49 r² + 14r +49 = 0 delta =196 − 49*4 = 0 r = −14/2 =−7 ...

Hugo: nie wiedziałem ze tak sie da dzięki a czy 5,6,7,8,9 któreś z tych byłbyś wstanie?

Adamm: 7) a_n − ciągi ternarne n−elementowe jak w zadaniu a_n+1 = 2a_n+1, a₁ = 3 1. jeśli pierwsza jest jedynka, to ciąg jedynek 2. jeśli pierwsza jest dwójka lub zero, to mamy dowolny ciąg n elementowy tej postaci

Adamm: 5) s_n = (An+B)(−7)ⁿ A, B z warunków początkowych

Adamm: 8) |A₆^c∩A₂₁^c∩A₃₅^c| = 9*10⁴−|A₆∪A₂₁∪A₃₅| potem wzór włączeń i wyłączeń

Adamm: ja idę spać, więcej ci dzisiaj nie pomogę

Hugo: @Adamm: czyli jak mamy 2 pierwiastki to: np. ( z innego zadania) gdy mamy delta > 0 to: C2 = (−4−6)/2 = −5 C1 = (−4+6)/2 = 1 sn = C2(−5)ⁿ + C1ⁿ a gdy mamy delta = 0 to: sn = (An+B)(−7)ⁿ

Hugo: dzieki za pomoc dobranoc

Adamm: Jak masz pierwiastek k−tego stopnia, to całość mnożysz przez wielomian k−1 stopnia Jakby 7 była potrójnym pierwiastkiem, to było s_n = (An²+Bn+C)7ⁿ etc

Hugo: s_n = (An+B)(−7)ⁿ s₀ =−1, s₁ = −14 −1 = (A*0 + B)(−7)⁰ −1 = B −14 = (A*1+B)(−7)¹ −14 = (A+B)(−7) /:(−7) 2 = A+B 2 = A −1 A = 3 s_n = (3n−1)(−7)ⁿ kurka wodna dobrze @Adamm dzięki

Hugo: tzn jak mamy delta >0 to AC₁ⁿ + BC₂ⁿ, a gdy delta = 0 to (An+B)*(r)ⁿ, tak średnio rozumiem to co napisałeś powyżej, zawsze (do tej pory) mam II stopień wielomianu gdyż sprowadzam do ar² + br + c = 0 chodzi o rozwiązanie delty. delta >0 delta = 0 i tu właśnie powiedziałeś że (An+B)(r)² delta <0 i strzelam że tak samo jak >0 tylko lecimy na √i² = −1 ale chyba innych rzeczy nie będzie z tymi niejednorodnymi trochę słabo

Hugo: 6) tu mam ciężką rekurencję i nie wiem jak s_n+1 = 24s_n −2s_n−1 + 25n*4ⁿ⁺¹ bez warunków początkowych juz nawet nie chodzi o tak ciężkie(?) bo prowadzący daje łatwiejsze, ale chętnie bym te niejednorodne coś poprzerabiał. Mila mi jednej przykład pokazała.

Hugo: umiał by ktoś 6) ?