Wiedząc, że \(\displaystyle{ 2^6\equiv7(mod19)}\) znaleźć wszystkie rozwiązania równania \(\displaystyle{ x^6\equiv7(mod19)}\)
Proszę o wskazówki z czego powinnam skorzystać, z jakich własności czy twierdzeń. Wiem, że może to mieć związek z pierwiastkami pierwotnymi, ale nie potrafię tego rozwiązać.
wiedząc, że.. znajdź rozwiązania kongruencji
-
- Użytkownik
- Posty: 20
- Rejestracja: 16 sty 2010, o 19:16
- Płeć: Kobieta
- Lokalizacja: Kraków
- SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
wiedząc, że.. znajdź rozwiązania kongruencji
Ja bym to robił tak- niech \(\displaystyle{ ord_{19} (a)}\) będzie rzędem liczby \(\displaystyle{ a}\) modulo \(\displaystyle{ 19}\). Wówczas, jeżeli \(\displaystyle{ ord_{19}(a)|6}\), to liczba \(\displaystyle{ 2a}\) jest rozwiązaniem Twojej kongruencji. Można wykazać, że takich liczb \(\displaystyle{ a}\) jest dokładnie 6.
-
- Użytkownik
- Posty: 20
- Rejestracja: 16 sty 2010, o 19:16
- Płeć: Kobieta
- Lokalizacja: Kraków
wiedząc, że.. znajdź rozwiązania kongruencji
Dziękuję. Znalazłam na forum rozwiązanie podobnego zadania, którego sposób rozwiązania jest jaśniejszy, czy jest poprawny?
\(\displaystyle{ \varphi(19)=18}\) zatem pierwiastek pierwotny\(\displaystyle{ a}\) musi spełniać:
\(\displaystyle{ a^1^8\equiv1(mod19)}\)
potencjalni kandydaci na p.pierwotny \(\displaystyle{ a \in [1,2,...,18]}\)
a jest p.pierwotnym\(\displaystyle{ (mod19) \Leftrightarrow}\) jego rząd w \(\displaystyle{ Z_1_9}\) jest równy rzędowi tej grupy, czyli \(\displaystyle{ 18}\).
rząd elementu dzieli rząd grupy zatem d=rząd,\(\displaystyle{ d \in [1,2,3,6,9,18]}\)
teraz muszę znaleźc takie a, dla którego \(\displaystyle{ a^6\not\equiv1(mod19)}\) i \(\displaystyle{ a^9\not\equiv1(mod19)}\) (wówczas wykluczę też \(\displaystyle{ a^2}\) i\(\displaystyle{ a^3}\)) jeżeli znajdę takie\(\displaystyle{ a}\), gdzie \(\displaystyle{ a \in [1,2,...,18]}\) to będzie ono pierwiastkiem pierwotnym\(\displaystyle{ (mod 19)}\)
i po obliczeniach dla \(\displaystyle{ a=2}\) powyższe kongruencje zachodzą, zatem\(\displaystyle{ 2}\) jest pierwiastkiem pierwotnym.
biorę sobie g, h takie, że: \(\displaystyle{ 2^g\equiv2(mod19)}\) i \(\displaystyle{ 2^h\equiv x(mod19)}\)
na mocy założeń:
\(\displaystyle{ 2^6^g\equiv7\equiv2^6^h(mod19)}\)
zatem\(\displaystyle{ 2^6^g\equiv2^6^h}\)
czyli \(\displaystyle{ g\equiv h}\) oraz \(\displaystyle{ 2\equiv2^g\equiv2^h\equivx}\) \(\displaystyle{ \Rightarrow}\) \(\displaystyle{ x=2}\)
Czy to jest okej?
\(\displaystyle{ \varphi(19)=18}\) zatem pierwiastek pierwotny\(\displaystyle{ a}\) musi spełniać:
\(\displaystyle{ a^1^8\equiv1(mod19)}\)
potencjalni kandydaci na p.pierwotny \(\displaystyle{ a \in [1,2,...,18]}\)
a jest p.pierwotnym\(\displaystyle{ (mod19) \Leftrightarrow}\) jego rząd w \(\displaystyle{ Z_1_9}\) jest równy rzędowi tej grupy, czyli \(\displaystyle{ 18}\).
rząd elementu dzieli rząd grupy zatem d=rząd,\(\displaystyle{ d \in [1,2,3,6,9,18]}\)
teraz muszę znaleźc takie a, dla którego \(\displaystyle{ a^6\not\equiv1(mod19)}\) i \(\displaystyle{ a^9\not\equiv1(mod19)}\) (wówczas wykluczę też \(\displaystyle{ a^2}\) i\(\displaystyle{ a^3}\)) jeżeli znajdę takie\(\displaystyle{ a}\), gdzie \(\displaystyle{ a \in [1,2,...,18]}\) to będzie ono pierwiastkiem pierwotnym\(\displaystyle{ (mod 19)}\)
i po obliczeniach dla \(\displaystyle{ a=2}\) powyższe kongruencje zachodzą, zatem\(\displaystyle{ 2}\) jest pierwiastkiem pierwotnym.
biorę sobie g, h takie, że: \(\displaystyle{ 2^g\equiv2(mod19)}\) i \(\displaystyle{ 2^h\equiv x(mod19)}\)
na mocy założeń:
\(\displaystyle{ 2^6^g\equiv7\equiv2^6^h(mod19)}\)
zatem\(\displaystyle{ 2^6^g\equiv2^6^h}\)
czyli \(\displaystyle{ g\equiv h}\) oraz \(\displaystyle{ 2\equiv2^g\equiv2^h\equivx}\) \(\displaystyle{ \Rightarrow}\) \(\displaystyle{ x=2}\)
Czy to jest okej?
- SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
wiedząc, że.. znajdź rozwiązania kongruencji
Zaraz wymyślę co jest nie tak, ale rozwiązaniem jest także \(\displaystyle{ 17}\), bo \(\displaystyle{ 17^6\equiv(-2)^6\equiv 2^6\equiv 7\pmod{19}}\).
EDIT:
Oczywiście u Ciebie \(\displaystyle{ g=1}\). Do momentu \(\displaystyle{ 2^6\equiv 2^{6h}}\) jest ok, ale z tego wynika \(\displaystyle{ 6\equiv 6h\pmod{19-1}}\), czyli \(\displaystyle{ 18|6(h-1)}\) oraz \(\displaystyle{ h\in\{1,2,\ldots,18\}}\), a takie \(\displaystyle{ h}\) już prosto znaleźć
EDIT:
Oczywiście u Ciebie \(\displaystyle{ g=1}\). Do momentu \(\displaystyle{ 2^6\equiv 2^{6h}}\) jest ok, ale z tego wynika \(\displaystyle{ 6\equiv 6h\pmod{19-1}}\), czyli \(\displaystyle{ 18|6(h-1)}\) oraz \(\displaystyle{ h\in\{1,2,\ldots,18\}}\), a takie \(\displaystyle{ h}\) już prosto znaleźć