Mam problem z obliczeniem reszty z dzielenia liczby \(\displaystyle{ 4847^{1525}}\) przez liczbe 407
MOD(\(\displaystyle{ 4847^{1525}}\), 407) Czy ktoś mógłby wytłumaczyć jak wykonać to zadanie?
reszta z dzielenia 4847^1525 przez liczbe 407 (MOD)
-
adambak
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
reszta z dzielenia 4847^1525 przez liczbe 407 (MOD)
liczby są niewygodne, ponieważ \(\displaystyle{ 4847}\) oraz \(\displaystyle{ 407}\) nie są względnie pierwsze co nam uniemożliwia skorzystanie z twierdzenia Eulera.. sugeruję zatem algorytm szybkiego potęgowania modulo \(\displaystyle{ 407}\), aż tak dużo liczenia to nie będzie..
-- 15 cze 2012, o 12:42 --
liczby jednak są dobre (na algorytm szybkiego potęgowania), reszty z dzielenia się zapętlają:
\(\displaystyle{ 4847\equiv_{407} 370\\
4847^2\equiv_{407} 148\\
4847^4\equiv_{407} 333\\
4847^8\equiv_{407} 185\\
4847^{16}\equiv_{407} 37\\
4847^{32}\equiv_{407} 148\\
4847^{64}\equiv_{407} 333\\
4847^{128}\equiv_{407} 185\\
4847^{256}\equiv_{407} 37\\
4847^{512}\equiv_{407} 148\\
4847^{1024}\equiv_{407} 333}\)
(dzięki zapętleniu nie musiałem liczyć pięciu ostatnich)
no to znając te reszty rozbijamy wykładnik: \(\displaystyle{ 1525=1024+256+128+64+32+16+4+1}\) i liczymy:
\(\displaystyle{ 333\cdot 37\cdot 185\cdot 333\cdot 148\cdot 37\cdot 333\cdot 370\equiv_{407} 296}\)
(co może wygląda strasznie, ale znów możemy wykorzystać poprzednie wyniki)
w takim razie: \(\displaystyle{ 4847^{1525}\equiv_{407} 296}\)
ogólnie schemat jest zawsze taki sam: liczymy reszty z dzielenia dla kolejnych potęg dwójki (podnosząc do kwadratu kolejno otrzymywane reszty), a potem wedle uznania rozbijamy wykładnik na sumę wykładników którymi "dysponujemy" i korzystając z podstawowych własności kongruencji liczymy wynik..
-- 15 cze 2012, o 12:42 --
liczby jednak są dobre (na algorytm szybkiego potęgowania), reszty z dzielenia się zapętlają:
\(\displaystyle{ 4847\equiv_{407} 370\\
4847^2\equiv_{407} 148\\
4847^4\equiv_{407} 333\\
4847^8\equiv_{407} 185\\
4847^{16}\equiv_{407} 37\\
4847^{32}\equiv_{407} 148\\
4847^{64}\equiv_{407} 333\\
4847^{128}\equiv_{407} 185\\
4847^{256}\equiv_{407} 37\\
4847^{512}\equiv_{407} 148\\
4847^{1024}\equiv_{407} 333}\)
(dzięki zapętleniu nie musiałem liczyć pięciu ostatnich)
no to znając te reszty rozbijamy wykładnik: \(\displaystyle{ 1525=1024+256+128+64+32+16+4+1}\) i liczymy:
\(\displaystyle{ 333\cdot 37\cdot 185\cdot 333\cdot 148\cdot 37\cdot 333\cdot 370\equiv_{407} 296}\)
(co może wygląda strasznie, ale znów możemy wykorzystać poprzednie wyniki)
w takim razie: \(\displaystyle{ 4847^{1525}\equiv_{407} 296}\)
ogólnie schemat jest zawsze taki sam: liczymy reszty z dzielenia dla kolejnych potęg dwójki (podnosząc do kwadratu kolejno otrzymywane reszty), a potem wedle uznania rozbijamy wykładnik na sumę wykładników którymi "dysponujemy" i korzystając z podstawowych własności kongruencji liczymy wynik..
-
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 4847^1525 przez liczbe 407 (MOD)
Da się szybciej bez żmudnych rachunków Wiemy, że \(\displaystyle{ 407 = 11\cdot 37}\), więc:
\(\displaystyle{ x \equiv 4847^{1525} \pmod{407} \\ \\ \iff \\ \\ \begin{cases} x \equiv 4847^{1525} \equiv 7^{1525} \pmod{11} \\ x \equiv 4847^{1525} \equiv 0\pmod{37} \end{cases}}\)
Ale z Małego Twierdzenia Fermata mamy \(\displaystyle{ 7^{10} \equiv 1\pmod{11}}\), więc:
\(\displaystyle{ x \equiv 7^{1525} \equiv 7^5 \cdot (7^{10})^{152} \equiv 7^5 \equiv 10\pmod{11}}\)
Czyli \(\displaystyle{ \begin{cases} x \equiv 10\pmod{11} \\ x \equiv 0\pmod{37} \end{cases}}\)
A stąd już łatwo dostać \(\displaystyle{ x \equiv 296\pmod{407}}\)
\(\displaystyle{ x \equiv 4847^{1525} \pmod{407} \\ \\ \iff \\ \\ \begin{cases} x \equiv 4847^{1525} \equiv 7^{1525} \pmod{11} \\ x \equiv 4847^{1525} \equiv 0\pmod{37} \end{cases}}\)
Ale z Małego Twierdzenia Fermata mamy \(\displaystyle{ 7^{10} \equiv 1\pmod{11}}\), więc:
\(\displaystyle{ x \equiv 7^{1525} \equiv 7^5 \cdot (7^{10})^{152} \equiv 7^5 \equiv 10\pmod{11}}\)
Czyli \(\displaystyle{ \begin{cases} x \equiv 10\pmod{11} \\ x \equiv 0\pmod{37} \end{cases}}\)
A stąd już łatwo dostać \(\displaystyle{ x \equiv 296\pmod{407}}\)