Kongruencje. Karolina11: Rozwiąż kongruencje x² − 3x + 3 ≡ 0 (mod 91). Z góry dziękuję za pomoc.

kerajs: Wskazówka: 91=7*13 więc x² − 3x + 3 ≡ 0 (mod 7) ⋀ x² − 3x + 3 ≡ 0 (mod 13) wynik: x=91m+n gdzie n∊{11;18;76;83} oraz m jest dowolną liczbą całkowitą.

Karolina11: Można poprosić o rozpisanie trochę dalej tego? Bo mi nie wychodzi. Z góry dziękuję.

Adamm: np. można spróbować odwrócić 2 2a = 1 (mod 7) 7 = 2*3+1 ⇒ 2*(−3) ≡ 1 (mod 7) teraz tak x² − 3x + 3 ≡ x² + 2*9x + 3 = (x+9)² − 78 ≡ (x+2)² − 1 = (x+1)(x+3) ≡ 0 (mod 7) skąd x ≡ 6 lub x ≡ 4 (mod 7) zatem odwracając 2, sprowadzamy problem do obliczania pierwiastków

Karolina11: Chciałam skorzystać z wskazówki i tę pierwsza kongruencje policzyłam, a drugiej nie potrafię... I nie wiem jak potem do "polaczyc" żeby powstały te wymienione odpowiedzi.

Szkolniak: 1) x²−3x+3≡0 (mod 7) x²−3x+3≡7 (mod 7) x²−3x−4≡0 (mod 7) (x−4)(x+1)≡0 (mod 7) x−4≡0 (mod 7), x+1≡0 (mod 7) x≡4 (mod 7), x≡=6 (mod 7) 2) x²−3x+3≡0 (mod 13) x−4≡0 (mod 13), x+1≡0 (mod 13) x≡4 (mod 13), x≡12 (mod 13) Ja bym doszedł do tego momentu, postaci x=91m+n nie jestem w stanie wytłumaczyć.

Adamm: inaczej można zrobić tak patrzymy x = 0, x = 1, x = 2, ... widzimy dla x = 4 że x²−3x+3 ≡ 0 (mod 7) dzielimy pisemnie x²−3x+3 = (x−4)(x+a)+... widzimy że −4+a = −3 więc a = 1

Adamm: @Szkolnik albo ty masz rację, albo kerajs bo z tego co ty napisałeś wynika że jedno z rozwiązań to x ≡ 25 (mod 91)

Adamm: 13 = 6*2+1 x²−3x+3 ≡ x²+2*6*3*x+3 ≡ x²+2*5*x+3 = (x+5)² − 22 ≡ (x+5)² − 9 = (x+2)(x+8) to mi wychodzi 11 i 5

chichi: @kerajs podał prawidłowy wynik

Adamm: x ≡ 4 lub 6 (mod 7) x ≡ 11 lub 5 (mod 13) x = 11+13y, y∊{0, ..., 6} 11+13y ≡ 4 (mod 7) ⇔ y ≡ 0 (mod 7) czyli tutaj x ≡ 11 (mod 91) x = 5+13y 5+13y ≡ 4 (mod 7) ⇔ y ≡ 1 (mod 7) tutaj x ≡ 18 (mod 91) x = 11+13y ≡ 6 (mod 7) ⇔ y ≡ 5 (mod 7) x ≡ 76 (mod 91) no i ostatnie to sobie sami policzcie

Mila: kerajs podał prawidłowe rozwiązania. Możecie sprawdzić podstawiając do równania. Po kolacji napiszę.

Szkolniak: W takim razie przepraszam za zamieszanie.

Mila: 1) x² − 3x + 3 ≡ 0 (mod 7) ⋀ x² − 3x + 3 ≡ 0 (mod 13) Małe moduły , to można na piechotę sprawdzić jakie są rozwiązania. x∊{4,6} i x∊{5,11} 2) Ja rozwiązywałam tak: 1) x=4(mod7) i x=5(mod13) x=4+7k i x=5+13m , m,k∊C 4+7k=5+13m 7k=13m+1 7k=1(mod13) / *2 [ odwrotna do 7 w z₁₃ to liczba 2] 7k*2= 2 (mod13) 1k=2(mod13) ⇔k=13m+2 podstawiam do równania x=4+7k x=4+7*(13m+2)=4+91m+14 x=91m+18 ======== Pozostałe Karolina rozwiąże sama? x=6+7k i x=5+13m 7k+6=13m+5 ⇔7k=(−1) (mod13) 7k=13m−1 /*2 14k=13s−2, s∊C 1k=13s−2 podstawiam do równania x=6+7k x=6+7*(13s−2)=6+91s−14 x=91s−8⇔ x=91s+83 ========

Mila: Można wypisać kolejno dla układu: x=4(mod7) i x=5(mod13) i badać reszty 1) k 0 1 2 3 x₍7) 4 11 18 25 r₁₃ 4 11 5 Już trafiona reszta 5 x=18+7*13s x=18+91s 2) x=4(mod7) i x=11(mod13) k 0 1 2 3 4 5 6 7 x ₇ 4 11 18 25 r 4 11 trafiona x=11+91s gorzej z pozostałymi będzie więcej liczenia

kerajs: a) Dotyczy: Karolina11 18:18 Zważywszy na ilość pomocnych postów chyba już nie muszę podawać kolejnych kroków. b) Dotyczy Szkolniak 18:47 : '' 2) x²−3x+3≡0 (mod 13) x−4≡0 (mod 13), x+1≡0 (mod 13) x≡4 (mod 13), x≡12 (mod 13) '' Liczyłbym tak; x²−3x+3≡0 (mod 13) x²−3x−10≡0 (mod 13) (x−5)(x+2)≡0 (mod 13) x≡5 (mod 13) lub x≡11 (mod 13)

Karolina11: Dziękuję wszystkim za pomoc, resztę policzyłam sama.