Witam, potrzebuję rozwiązać następujące zadanie:
W ciele \(\displaystyle{ Z_{31}}\) oblicz \(\displaystyle{ 4 \cdot 17^{-3}+3^{2011}}\)
czyli mam wliczyć \(\displaystyle{ x}\) dla:
\(\displaystyle{ x = 4 \cdot 17^{-3}+3^{2011} \left( mod 31\right)}\)
Gdzie \(\displaystyle{ x}\) to reszta z dzielenia.
Zadanie to należy wykonać przy pomocy twierdzeń, bez pomocy kalkulatora.
Z kalkulatorem potrafię wyliczyć, ale jedynie druga część równania czyli \(\displaystyle{ 3^{2011}}\).
Prosiłbym o pomoc w rozwiązaniu tego zadania. Próbowałem coś z Małym tw. Fermata itp., ale nic nie pasuje wg. mnie do rozwiązania tego zadanka.
Kongruencja w podanym ciele.
-
SanczoPanczo
- Użytkownik
- Posty: 69
- Rejestracja: 5 gru 2010, o 01:35
- Płeć: Mężczyzna
- Lokalizacja: gdzieś pomiędzy okresami sin(x)
- Podziękował: 23 razy
Kongruencja w podanym ciele.
Ostatnio zmieniony 11 lut 2011, o 13:45 przez Qń, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości i nazwy tematu.
Powód: Poprawa wiadomości i nazwy tematu.
-
sebnorth
- Użytkownik
- Posty: 635
- Rejestracja: 12 sty 2011, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Puck i Trójmiasto
- Pomógł: 201 razy
Kongruencja w podanym ciele.
\(\displaystyle{ NWD(31,17)=1}\)
Z algorytmu Euklidesa dostajemy: \(\displaystyle{ 1 = 11 \cdot 17 - 6 \cdot 31}\)
Czyli w danym ciele to będzie równość \(\displaystyle{ 1 = 11 \cdot 17. \hbox{ Czyli } 17^{-1} = 11, 17^{-3} = 11^{3} = 29}\).
Z drugiej strony na mocy małego twierdzenia Fermata mamy:
\(\displaystyle{ mod(3^{30},31) = 1, \ mod((3^{30})^{67},31) = 1, \ mod(3^{2010},31) = 1, \ mod(3^{2011},31) = 3}\)
itd
Z algorytmu Euklidesa dostajemy: \(\displaystyle{ 1 = 11 \cdot 17 - 6 \cdot 31}\)
Czyli w danym ciele to będzie równość \(\displaystyle{ 1 = 11 \cdot 17. \hbox{ Czyli } 17^{-1} = 11, 17^{-3} = 11^{3} = 29}\).
Z drugiej strony na mocy małego twierdzenia Fermata mamy:
\(\displaystyle{ mod(3^{30},31) = 1, \ mod((3^{30})^{67},31) = 1, \ mod(3^{2010},31) = 1, \ mod(3^{2011},31) = 3}\)
itd