Reszta z dzielenia
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
Reszta z dzielenia
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ć?
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.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
- 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
Reszta z dzielenia
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}}\)
\(\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}}\)
-
- Użytkownik
- Posty: 111
- Rejestracja: 30 maja 2012, o 18:49
- Płeć: Mężczyzna
- Lokalizacja: Podlaskie
- Podziękował: 8 razy
- Pomógł: 9 razy
Reszta z dzielenia
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ć?
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ć?
-
- Użytkownik
- Posty: 111
- Rejestracja: 30 maja 2012, o 18:49
- Płeć: Mężczyzna
- Lokalizacja: Podlaskie
- Podziękował: 8 razy
- Pomógł: 9 razy
Reszta z dzielenia
\(\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}\)
\(\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].
Powód: Nie zagnieżdżaj tagów [b] w