Kongruencja, pierwiastki pierwotne

[dzb]

Witajcie,
mam problem z taką oto kongruencją:

\(\displaystyle{ x^{8} \equiv 10 mod 31}\)

Z tego co wiem, należy znaleźć pierwiastek pierwotny modulo 31. Jednym z nich jest 3.
Następnie prawą stronę przedstawiam jako potęgę pierwiastka pierwotnego.
Wyszło mi, że:

\(\displaystyle{ 3 ^{14} \equiv 10 mod 31}\)

Więc:

\(\displaystyle{ x^{8} \equiv 3 ^{14} mod 31}\)

Teraz wszystko logarytmuje, i obie strony przystają do siebie modulo wartość funkcji Eulera od 31 czyli 30:

\(\displaystyle{ 8log _{3}x \equiv 14 mod 30}\)

I tu mam problem.
Potrzebuję mieć wartość:

\(\displaystyle{ log _{3}x}\)

Chciałbym się pozbyć 8 stojącej przy nim. Rozumiem, że powinienem pomnożyć obie strony przez jej odwrotność modulo 30. Ale przecież 8 nie posiada odwrotności mod 30, gdyż nie jest z 30 względnie pierwsza.
Co teraz powinienem zrobić?
A może kongruencja nie posiada rozwiązań? (w zadaniu było napisane "znajdź rozwiązania jeśli istnieją"). Jeśli tak to z czego to wynika?

Proszę o pomoc.
Z góry dziękuję i pozdrawiam.

[arek1357]

Strasznie zagmatwałeś ale spróbuję ro rozwikłać, sądzę że w ostatnim chodzi o mod 31 a nie mod 30

uporządkuijmy czyli chcesz obliczyć:

\(\displaystyle{ log_{3}x=8^{-1}*14=4*14=56=25}\)

oczywiście równości są modulo-- 6 stycznia 2012, 00:24 --A swoją drogą z tymi logarytmami to dałeś czadu!

[dzb]

Dzięki za próbę rozwikłania.
Widzę, że znalazłeś odwrotność 8 modulo 31 tj. 4.

Ale w:
\(\displaystyle{ 8log _{3}x \equiv 14 mod 30}\)
wydaje mi się, że powinno być modulo 30.

Jest własność następująca:
\(\displaystyle{ x_{1} \equiv x_{2} mod n \Leftrightarrow log_{g}x_{1} \equiv log_{g} x_{2} mod \phi\left( n\right)}\)

Gdzie g jest generatorem grupy.

\(\displaystyle{ \phi\left( 31\right) = 30}\) (bo 31 jest l. pierwszą)

No i właśnie co tu począć? 8 nie będzie miało liczby odwrotnej mod 30 bo te liczby nie są względnie pierwsze.


BTW. Dlaczego "dałem czadu" z logarytmami?

[arek1357]

W modulo 30 tylko te elementu są odwrotne co są z 30 względnie pierwsze i one tworza grupę!
8 nie ma elementu odwrotnego bo nie jest z 30 względnie pierwsza!

[dzb]

Właśnie to napisałem. I co tu zrobić?
Po zlogarytmowaniu zmieniam mod z 31 na 30 ( \(\displaystyle{ \phi\left( 31\right)}\) ).
I wtedy nie mogę odwrócić ósemki...

[arek1357]

Nie rozumiem poco zmieniasz modulo 31 na modulo 31 to dla mnie bardzo dziwne i czemu to służyć ma??

[dzb]

Wynika to z własności, którą wziąłem z moich notatek:

\(\displaystyle{ x_{1} \equiv x_{2} \mod n \Leftrightarrow \log_{g}x_{1} \equiv \log_{g} x_{2} \mod \phi\left( n\right)}\)

W innych zadaniach, które robiliśmy na ćwiczeniach też zamienialiśmy mod po zlogarytmowaniu.
Ale zawsze wychodziły liczby względnie pierwsze i można było odwrócić modulo.

[abc666]

dzb, jeśli \(\displaystyle{ ad\equiv bd \pmod{cd}}\) to \(\displaystyle{ a\equiv b \pmod{c}}\) oraz jeśli
\(\displaystyle{ a\equiv b \pmod{dp}}\) gdzie \(\displaystyle{ p}\) jest pierwsza to \(\displaystyle{ a\equiv b \pmod{p}}\)

[arek1357]

3=8 mod 5 jeśli zachodzi to
to według tego wzoru powinno zachodzić również i to:

\(\displaystyle{ lg_{3}3=lg_{3}8 (mod4)}\)
czyli 3 do x wychodzi 0 bzdura

co to za wzór coś się to dla mnie wydaje dziwne

[dzb]

Dzięki abc666
Skorzystałem z własności:
\(\displaystyle{ ad\equiv bd \pmod{cd} to a\equiv b \pmod{c}}\)

i mam:
\(\displaystyle{ 8log _{3}x \equiv 14 mod 30}\)

\(\displaystyle{ 4log _{3}x \equiv 7 mod 15}\)

Odwrotną liczbą do 4 modulo 15 jest 4.


\(\displaystyle{ log _{3}x \equiv 4 \cdot 7 mod 15}\)

\(\displaystyle{ log _{3}x \equiv 13 mod 15}\)

\(\displaystyle{ x = 3^{13}}\)

Sprawdzałem podstawiając i jest ok.

[abc666]

Tylko jest jeszcze taki problem, że ta kongruencja ma dwa rozwiązania. Jak uzyskać drugie, powiem szczerze, że nie wiem.

[Zordon]

Pisanie takich logarytmów jest zdecydowanie niepożądane. Zupełnie wystarcza takie rozumowanie:
\(\displaystyle{ x}\) jest pewną potęgą 3, zatem niech \(\displaystyle{ x=3^{y}}\). Nasze równanie przepisuje się jako:
\(\displaystyle{ 3^{8y}=3^{14} \pmod{31}}\).
Co jak słusznie zauważyłeś jest równoważne temu, że:
\(\displaystyle{ 8y = 14\pmod{30}}\)
Tutaj dostajemy kongruencję liniową, jest pewnie znany algorytm ich rozwiązywania, ale przypomnę:
Wydzielamy przez \(\displaystyle{ nwd(8,30)=2}\), \(\displaystyle{ 2|14}\) zatem będą 2 rozwiązania. Przechodzimy do równania:
\(\displaystyle{ 4y = 7\pmod{15}}\)
\(\displaystyle{ y = 13\pmod{15}}\)
Stąd:
\(\displaystyle{ y = 13,13+15\pmod{30}}\)

Stąd mamy dwa rozwiazania: \(\displaystyle{ 3^{13},3^{28}}\)

[arek1357]

Brawo Zordon dobrze że posprzątałeś ten bałagan-- 9 stycznia 2012, 12:35 --Dodam tylko że te liczby to 24 i 7