wiedząc, że.. znajdź rozwiązania kongruencji

[roseraphina]

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ć.

[SaxoN]

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.

[roseraphina]

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?

[SaxoN]

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źć