szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 19 cze 2012, o 19:13 
Użytkownik

Posty: 50
Lokalizacja: Polska
Obliczyć resztę z dzielenia liczby 2^{1000} przez 77

Mógłby mi ktoś krok po kroku wyjaśnić w jaki sposób to robić?
Góra
Mężczyzna Offline
PostNapisane: 19 cze 2012, o 19:21 
Użytkownik
Avatar użytkownika

Posty: 2909
Lokalizacja: Biała Podlaska / Warszawa
Chcemy znaleźć:

x \equiv 2^{1000} \pmod{77}

Ale 77 = 7\cdot 11, więc jest to równoważne:

\begin{cases} x \equiv 2^{1000} \pmod{7} \\ x \equiv 2^{1000} \pmod{11} \end{cases}

W 1 kongruencji zauważamy, że 2^3 \equiv 1\pmod{7}/^{333} \Rightarrow 2^{999} \equiv 1\pmod{7} /\cdot 2 \Rightarrow 2^{1000} \equiv 2\pmod{7}

W 2 kongruencji zauważamy, że z Małego Twierdzenia Fermata 2^{10} \equiv 1\pmod{11}/^{100} \Rightarrow 2^{1000} \equiv 1\pmod{11}, więc otrzymujemy:

\begin{cases} x \equiv 2\pmod{7} \\ x \equiv 1 \pmod{11} \end{cases}

Skąd otrzymujemy x \equiv 23\pmod{77}
Góra
Kobieta Offline
PostNapisane: 19 cze 2012, o 19:29 
Użytkownik

Posty: 50
Lokalizacja: Polska
Jakiś inne sposób? Bo tego kompletnie nie rozumiem...
Góra
Mężczyzna Offline
PostNapisane: 19 cze 2012, o 19:32 
Użytkownik

Posty: 111
Lokalizacja: Podlaskie
a wiesz co oznacz mod?
Góra
Kobieta Offline
PostNapisane: 19 cze 2012, o 19:33 
Użytkownik

Posty: 50
Lokalizacja: Polska
Tak wiem co to oznacza.
Góra
Mężczyzna Offline
PostNapisane: 19 cze 2012, o 19:35 
Użytkownik

Posty: 111
Lokalizacja: Podlaskie
w taki razie musisz wyznaczyć 2^{1000} \mod 77
Góra
Kobieta Offline
PostNapisane: 19 cze 2012, o 19:36 
Użytkownik

Posty: 50
Lokalizacja: Polska
Tyle to ja wiem... Ale w jaki sposób?
Góra
Mężczyzna Offline
PostNapisane: 19 cze 2012, o 19:41 
Użytkownik

Posty: 111
Lokalizacja: Podlaskie
najlepiej znaleźć \alpha taki, że 2^ {\alpha }\equiv 1 \mod 77

ponieważ to nie takie proste, najlepiej rozbić jedną kongruencje na układ dwóch
stąd
patrzysz do ilu liczba 2^{1000}przystaje w \mod 7
oraz w \mod 11

-- 19 cze 2012, o 20:44 --

2^{1000} w modulo 7 przystaje do ??

-- 19 cze 2012, o 20:49 --

Do ilu liczba przystaje w mod 7?

-- 19 cze 2012, o 20:55 --

wiesz?? czy ci powiedzieć?
Góra
Kobieta Offline
PostNapisane: 19 cze 2012, o 20:10 
Użytkownik

Posty: 50
Lokalizacja: Polska
nie wiem
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2012, o 07:40 
Użytkownik

Posty: 111
Lokalizacja: Podlaskie
2^3=8\equiv 1 \mod 7
\left( 2^3\right) ^{333}\equiv 1^{333}\equiv 1 \mod 7

2^{1000}=2\cdot 2^{999}\equiv 2 \mod 7

Teraz utalmy do ilu przystaje 2^{1000} w \mod 11

2^{5}=32\equiv -1 \mod 11

2^{1000}=\left( 2^{5}\right) ^{200}=\left(-1 \right)^{200}\equiv 1 \mod 11


Dlatego 2^{1000} to liczba, która :
przystaje do 2 w \mod 7
przystaje do 1 w \mod 11

Liczby, które przystają do 2 w \mod 7 można wypisać: 2,9,16,\mathbf{23},30,37,44,51,...
Liczby, które przystaje do 1 w \mod 11 również wypiszmy: 1,12,\mathbf{23},34,45,...

Dlatego liczba jednocześnie spełniająca te dwa warunki to 23
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Reszta z dzielenia - zadanie 138  SirSwistak  1
 Reszta z dzielenia - zadanie 26  bujal  2
 Reszta z dzielenia - zadanie 9  Hoa Xang  4
 reszta z dzielenia - zadanie 90  dora1255  14
 reszta z dzielenia - zadanie 33  Ilonka  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl