Reszta z dzielenia

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska

Reszta z dzielenia

Post autor: menrva » 19 cze 2012, o 20:13

Obliczyć resztę z dzielenia liczby \(\displaystyle{ 2^{1000}}\) przez \(\displaystyle{ 77}\)

Mógłby mi ktoś krok po kroku wyjaśnić w jaki sposób to robić?
Ostatnio zmieniony 20 cze 2012, o 09:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa

Reszta z dzielenia

Post autor: Vax » 19 cze 2012, o 20:21

Chcemy znaleźć:

\(\displaystyle{ x \equiv 2^{1000} \pmod{77}}\)

Ale \(\displaystyle{ 77 = 7\cdot 11}\), więc jest to równoważne:

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

W 1 kongruencji zauważamy, że \(\displaystyle{ 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 \(\displaystyle{ 2^{10} \equiv 1\pmod{11}/^{100} \Rightarrow 2^{1000} \equiv 1\pmod{11}}\), więc otrzymujemy:

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

Skąd otrzymujemy \(\displaystyle{ x \equiv 23\pmod{77}}\)

menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska

Reszta z dzielenia

Post autor: menrva » 19 cze 2012, o 20:29

Jakiś inne sposób? Bo tego kompletnie nie rozumiem...

Forte
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 30 maja 2012, o 18:49
Płeć: Mężczyzna
Lokalizacja: Podlaskie

Reszta z dzielenia

Post autor: Forte » 19 cze 2012, o 20:32

a wiesz co oznacz \(\displaystyle{ mod}\)?

menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska

Reszta z dzielenia

Post autor: menrva » 19 cze 2012, o 20:33

Tak wiem co to oznacza.

Forte
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 30 maja 2012, o 18:49
Płeć: Mężczyzna
Lokalizacja: Podlaskie

Reszta z dzielenia

Post autor: Forte » 19 cze 2012, o 20:35

w taki razie musisz wyznaczyć \(\displaystyle{ 2^{1000} \mod 77}\)

menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska

Reszta z dzielenia

Post autor: menrva » 19 cze 2012, o 20:36

Tyle to ja wiem... Ale w jaki sposób?

Forte
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 30 maja 2012, o 18:49
Płeć: Mężczyzna
Lokalizacja: Podlaskie

Reszta z dzielenia

Post autor: Forte » 19 cze 2012, o 20:41

najlepiej znaleźć \(\displaystyle{ \alpha}\) taki, że \(\displaystyle{ 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 \(\displaystyle{ 2^{1000}}\)przystaje w \(\displaystyle{ \mod 7}\)
oraz w \(\displaystyle{ \mod 11}\)

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

\(\displaystyle{ 2^{1000}}\) w modulo \(\displaystyle{ 7}\) przystaje do ??

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

Do ilu liczba przystaje w \(\displaystyle{ mod 7}\)?-- 19 cze 2012, o 20:55 --wiesz?? czy ci powiedzieć?

menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska

Reszta z dzielenia

Post autor: menrva » 19 cze 2012, o 21:10

nie wiem

Forte
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 30 maja 2012, o 18:49
Płeć: Mężczyzna
Lokalizacja: Podlaskie

Reszta z dzielenia

Post autor: Forte » 20 cze 2012, o 08:40

\(\displaystyle{ 2^3=8\equiv 1 \mod 7}\)
\(\displaystyle{ \left( 2^3\right) ^{333}\equiv 1^{333}\equiv 1 \mod 7}\)

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

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

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

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


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

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

Dlatego liczba jednocześnie spełniająca te dwa warunki to \(\displaystyle{ 23}\)
Ostatnio zmieniony 20 cze 2012, o 09:37 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nie zagnieżdżaj tagów [b] w [latex].

ODPOWIEDZ