Witam, mam takie pytanie:
Jak wyznaczyć x z poniższej kongruencji:
\(\displaystyle{ 2^{x} \equiv30(mod37)}\)
Za pomoc serdecznie dziękuję.
kongruencja modulo 37, x w potędze
-
mikroice90
- Użytkownik
- Posty: 4
- Rejestracja: 23 sty 2011, o 15:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
kongruencja modulo 37, x w potędze
Ostatnio zmieniony 23 sty 2011, o 18:01 przez Crizz, łącznie zmieniany 1 raz.
Powód: Nie stosuj wzorów matematycznych w nazwie tematu.
Powód: Nie stosuj wzorów matematycznych w nazwie tematu.
-
Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
kongruencja modulo 37, x w potędze
\(\displaystyle{ 2^x \equiv 30 \pmod{37} \iff 2^{x-1} \equiv 15\pmod{37}}\)
Na początku zauważmy, że \(\displaystyle{ 2}\) jest generatorem \(\displaystyle{ \mathbb{Z}_{37}}\), istotnie, z Małego Twierdzenia Fermata rząd \(\displaystyle{ 2}\) musiałby dzielić \(\displaystyle{ 36}\) i jak łatwo ręcznie sprawdzić musi być równy \(\displaystyle{ 36}\). Znajdźmy takie \(\displaystyle{ 0 \le y < 36}\), że \(\displaystyle{ 2^y \cdot 15 \equiv 1\pmod{37}}\):
\(\displaystyle{ 2^y \cdot 15 \equiv 1\pmod{37} /\cdot 5 \iff 2^y \equiv 5 \equiv -2^5 \pmod{37} \iff 2^{y-5} \equiv -1 \pmod{37}}\)
Ale \(\displaystyle{ 2^{\frac{37-1}{2}} \equiv 2^{18} \equiv -1 \pmod{37}}\) (gdyż \(\displaystyle{ 2^{18} = 2^{\frac{37-1}{2}} = \left(\frac{2}{37}\right) = \pm 1}\) i nie może być równe \(\displaystyle{ 1}\), ponieważ jak zauważyliśmy \(\displaystyle{ 2}\) jest generatorem i \(\displaystyle{ 2^{36} \equiv 1\pmod{37}}\)).
Więc \(\displaystyle{ y-5 = 18 \iff y = 23}\), więc:
\(\displaystyle{ 2^{x-1} \equiv 15\pmod{37} /\cdot 2^{23} \iff 2^{x+22} \equiv 1 \equiv 2^{36} \pmod{37}}\)
A stąd \(\displaystyle{ x+22 \equiv 36 \pmod{36} \iff x \equiv 14 \pmod{36}}\)
Na początku zauważmy, że \(\displaystyle{ 2}\) jest generatorem \(\displaystyle{ \mathbb{Z}_{37}}\), istotnie, z Małego Twierdzenia Fermata rząd \(\displaystyle{ 2}\) musiałby dzielić \(\displaystyle{ 36}\) i jak łatwo ręcznie sprawdzić musi być równy \(\displaystyle{ 36}\). Znajdźmy takie \(\displaystyle{ 0 \le y < 36}\), że \(\displaystyle{ 2^y \cdot 15 \equiv 1\pmod{37}}\):
\(\displaystyle{ 2^y \cdot 15 \equiv 1\pmod{37} /\cdot 5 \iff 2^y \equiv 5 \equiv -2^5 \pmod{37} \iff 2^{y-5} \equiv -1 \pmod{37}}\)
Ale \(\displaystyle{ 2^{\frac{37-1}{2}} \equiv 2^{18} \equiv -1 \pmod{37}}\) (gdyż \(\displaystyle{ 2^{18} = 2^{\frac{37-1}{2}} = \left(\frac{2}{37}\right) = \pm 1}\) i nie może być równe \(\displaystyle{ 1}\), ponieważ jak zauważyliśmy \(\displaystyle{ 2}\) jest generatorem i \(\displaystyle{ 2^{36} \equiv 1\pmod{37}}\)).
Więc \(\displaystyle{ y-5 = 18 \iff y = 23}\), więc:
\(\displaystyle{ 2^{x-1} \equiv 15\pmod{37} /\cdot 2^{23} \iff 2^{x+22} \equiv 1 \equiv 2^{36} \pmod{37}}\)
A stąd \(\displaystyle{ x+22 \equiv 36 \pmod{36} \iff x \equiv 14 \pmod{36}}\)