Rozwiązać równanie w ciele Z11
-
- Użytkownik
- Posty: 53
- Rejestracja: 12 lut 2017, o 10:07
- Płeć: Mężczyzna
- Lokalizacja: tu
- Podziękował: 5 razy
Rozwiązać równanie w ciele Z11
Mam rozwiązać równanie w ciele \(\displaystyle{ \ZZ_{11}}\). Na początku myślałem, że muszę wyznaczyć pierwiastki i potem przyrównać do modulo \(\displaystyle{ 11}\) ale pierwiastki wyszły mi niewymierne i raczej moje myślenie jest błędne, podpowie ktoś jak to zrobić?
\(\displaystyle{ 5x^{2} +5x+1=0}\)
\(\displaystyle{ 5x^{2} +5x+1=0}\)
Ostatnio zmieniony 29 kwie 2019, o 13:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Rozwiązać równanie w ciele Z11
Masz obliczyć/sprawdzić dla jakich \(\displaystyle{ x}\) z \(\displaystyle{ \ZZ_{11}}\) zachodzi równość/przystawanie :
\(\displaystyle{ (5x^{2} +5x+1) \mod 11=0}\)
\(\displaystyle{ (5x^{2} +5x+1) \mod 11=0}\)
wynik:
Ostatnio zmieniony 29 kwie 2019, o 13:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Rozwiązać równanie w ciele Z11
Można po prostu podstawić na pałę elementy \(\displaystyle{ \ZZ_{11}}\) i sprawdzić, które pasują.
Jak nie chcesz tak robić, to pozostają jakieś sztuczki, na przykład można zauważyć, że w \(\displaystyle{ \ZZ_{11}}\) zachodzi \(\displaystyle{ 5x^2+5x+1=(8x+3)(2x+4)}\) i ponieważ \(\displaystyle{ 11}\) jest liczbą pierwszą, zatem by ten iloczyn się zerował, któryś z czynników musi być zerem modulo \(\displaystyle{ 11}\), tj.
\(\displaystyle{ 8x+3\equiv 0\pmod{11}}\) (co daje \(\displaystyle{ 1}\)) lub \(\displaystyle{ 2x+4\equiv 0\pmod{11}}\) (co daje \(\displaystyle{ 9}\)). Te dwa ostatnie równania można znaleźć, znajdując odwrotność odpowiednio liczby \(\displaystyle{ 8}\) i liczby \(\displaystyle{ 2}\) w \(\displaystyle{ \ZZ_{11}}\) i mnożąc przez te odwrotności odpowiednie równania (standardowo te odwrotności znajdujesz rozszerzonym algorytmem Euklidesa, choć tutaj szybciej zgadnąć).
Jak nie chcesz tak robić, to pozostają jakieś sztuczki, na przykład można zauważyć, że w \(\displaystyle{ \ZZ_{11}}\) zachodzi \(\displaystyle{ 5x^2+5x+1=(8x+3)(2x+4)}\) i ponieważ \(\displaystyle{ 11}\) jest liczbą pierwszą, zatem by ten iloczyn się zerował, któryś z czynników musi być zerem modulo \(\displaystyle{ 11}\), tj.
\(\displaystyle{ 8x+3\equiv 0\pmod{11}}\) (co daje \(\displaystyle{ 1}\)) lub \(\displaystyle{ 2x+4\equiv 0\pmod{11}}\) (co daje \(\displaystyle{ 9}\)). Te dwa ostatnie równania można znaleźć, znajdując odwrotność odpowiednio liczby \(\displaystyle{ 8}\) i liczby \(\displaystyle{ 2}\) w \(\displaystyle{ \ZZ_{11}}\) i mnożąc przez te odwrotności odpowiednie równania (standardowo te odwrotności znajdujesz rozszerzonym algorytmem Euklidesa, choć tutaj szybciej zgadnąć).
- Janusz Tracz
- Użytkownik
- Posty: 4075
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Rozwiązać równanie w ciele Z11
Dla liczb pierwszych postaci \(\displaystyle{ p=4k+3}\) (czyli na przykład \(\displaystyle{ 11}\) gdy \(\displaystyle{ k=2}\)) zachodzi ogólnie:
\(\displaystyle{ \left( a^{k+1}\right)^2\equiv a\bmod p}\)
Zauważając, że \(\displaystyle{ 20}\) nie dzieli się przez \(\displaystyle{ 11}\) można zapisać, że:
\(\displaystyle{ 20(5x^{2} +5x+1)\equiv 0\bmod11}\)
A to pozwala zapisać
\(\displaystyle{ \left( 10x+5\right)^2 \equiv 5 \bmod11}\)
czyli
\(\displaystyle{ 10x+5=5^3}\)
lub
\(\displaystyle{ 10x+5=-5^3}\)
stąd dostajemy, że \(\displaystyle{ x=12}\) czyli w \(\displaystyle{ \ZZ_{11}}\) po prostu \(\displaystyle{ 1}\) a z drugiego mamy \(\displaystyle{ x=-13}\) czyli w \(\displaystyle{ \ZZ_{11}}\) jest to \(\displaystyle{ 9}\)
\(\displaystyle{ \left( a^{k+1}\right)^2\equiv a\bmod p}\)
Zauważając, że \(\displaystyle{ 20}\) nie dzieli się przez \(\displaystyle{ 11}\) można zapisać, że:
\(\displaystyle{ 20(5x^{2} +5x+1)\equiv 0\bmod11}\)
A to pozwala zapisać
\(\displaystyle{ \left( 10x+5\right)^2 \equiv 5 \bmod11}\)
czyli
\(\displaystyle{ 10x+5=5^3}\)
lub
\(\displaystyle{ 10x+5=-5^3}\)
stąd dostajemy, że \(\displaystyle{ x=12}\) czyli w \(\displaystyle{ \ZZ_{11}}\) po prostu \(\displaystyle{ 1}\) a z drugiego mamy \(\displaystyle{ x=-13}\) czyli w \(\displaystyle{ \ZZ_{11}}\) jest to \(\displaystyle{ 9}\)
- Psiaczek
- Użytkownik
- Posty: 1502
- Rejestracja: 22 lis 2010, o 09:53
- Płeć: Mężczyzna
- Lokalizacja: Polska, Warmia, Olsztyn :)
- Podziękował: 1 raz
- Pomógł: 475 razy
Rozwiązać równanie w ciele Z11
a możesz też po prostu liczyć nieśmiertelną deltą tylko działania w \(\displaystyle{ \ZZ _{11}}\) czyli
\(\displaystyle{ \Delta=5^2-4 \cdot 5 \cdot 1=3-9=-6=5, \sqrt{\Delta}=7}\)
\(\displaystyle{ x _{1}= \frac{-5-7}{10}= \frac{6+4}{10}=1}\)
\(\displaystyle{ x _{2}= \frac{-5+7}{10}= \frac{2}{10}=2 \cdot 10=9}\) bo \(\displaystyle{ 10^{-1}=10}\)
\(\displaystyle{ \Delta=5^2-4 \cdot 5 \cdot 1=3-9=-6=5, \sqrt{\Delta}=7}\)
\(\displaystyle{ x _{1}= \frac{-5-7}{10}= \frac{6+4}{10}=1}\)
\(\displaystyle{ x _{2}= \frac{-5+7}{10}= \frac{2}{10}=2 \cdot 10=9}\) bo \(\displaystyle{ 10^{-1}=10}\)
Ostatnio zmieniony 29 kwie 2019, o 13:37 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 53
- Rejestracja: 12 lut 2017, o 10:07
- Płeć: Mężczyzna
- Lokalizacja: tu
- Podziękował: 5 razy
Rozwiązać równanie w ciele Z11
Super sposób, nie rozumiem tylko dlaczego pierwiastek z delty jest równy \(\displaystyle{ 7}\)?Psiaczek pisze:a możesz też po prostu liczyć nieśmiertelną deltą tylko działania w \(\displaystyle{ \ZZ _{11}}\) czyli
\(\displaystyle{ \Delta=5^2-4 \cdot 5 \cdot 1=3-9=-6=5, \sqrt{\Delta}=7}\)
\(\displaystyle{ x _{1}= \frac{-5-7}{10}= \frac{6+4}{10}=1}\)
\(\displaystyle{ x _{2}= \frac{-5+7}{10}= \frac{2}{10}=2 \cdot 10=9}\) bo \(\displaystyle{ 10^{-1}=10}\)
-- 29 kwi 2019, o 12:11 --
Już chyba wiem, chodzi o poniższy zapis?
\(\displaystyle{ (5+4 \cdot 11) \pmod{11}}\)
Ostatnio zmieniony 29 kwie 2019, o 13:38 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.