modulo z dzielenia dwóch liczb

[humphreyhojo]

Witam, mam problem z obliczeniem modulo z dzielenia liczby: \(\displaystyle{ 4847^{1525}}\) przez liczbę 407

Nie mam pojęcia jak to policzyć. Mam notatki według których ktoś najpierw dzieli liczbę 1525 na 2, następnie 762 itd do samego 0, kolejno sprawdzajac czy jest reszta z dzielenia.
Kolejnym krokiem jest podzielenie 4847 przez 407 i pomnożenie reszty z wyniku z 407. Dalej się w tym gubię. Czy ktoś mógłby mi to wytłumaczyć?

[Premislav]

\(\displaystyle{ 4847=37 \cdot (11 ^{2}+10)}\)
\(\displaystyle{ 407=37 \cdot 11}\)
jak dla mnie łatwiej to wykorzystać (+ przystawanie modulo i pewne jego własności, które w miarę łatwo wykazać) niż bawić się jakimś algorytmem, który nie bardzo zrozumiałem, ale może błądzę.
Mógłbyś jaśniej przedstawić treść tych notatek?

[Vax]

A dokładnie to: \(\displaystyle{ 4847^{1525} \equiv 370^{1525} \pmod{407}}\)

Jednak \(\displaystyle{ 407 = 11\cdot 37}\), na mocy chińskiego twierdzenia o resztach wiemy, że istnieje dokładnie jedno takie x, że:

\(\displaystyle{ \begin{cases} x \equiv 370^{1525} \equiv 7^{1525} \pmod{11} \\ x \equiv 370^{1525} \equiv 0\pmod{37}\end{cases}}\)

Ale z małego twierdzenia Fermata \(\displaystyle{ 7^{10} \equiv 1\pmod{11}}\) więc \(\displaystyle{ x \equiv 7^{1525} \equiv (7^{10})^{152}\cdot 7^5 \equiv 7\cdot 49^2 \equiv 7\cdot 5^2 \equiv 7\cdot 3 \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 wyliczyć \(\displaystyle{ x \equiv 296\pmod{407}}\)

[humphreyhojo]

Świetnie. Wielkie dzięki!-- 27 sie 2012, o 20:57 --

\(\displaystyle{ x \equiv 296\pmod{407}}\)

Można jeszcze wiedzieć jak wyliczyłeś 296 ?