Matematyka.pl

Witam, jak znajdowac reszty z dzielenia ogromnych liczb? Np mam zadanie reszta z dzielnia 222...22 (i tak 100 dwójek) przez 7 wynosi? Jak takie coś liczyć?

Stosowane są różne metody i sztuczki (spostrzeżenia).

Wykorzystam że \(\displaystyle{ 1001}\) jest podzielne przez \(\displaystyle{ 7}\). Oznacza to że liczba:
\(\displaystyle{ 200200+20020+2002=222222}\) jakże jest podzielna przez \(\displaystyle{ 7}\).
W 100 cyfrach mam 16 takich ,,szóstek' (podzielnych przez \(\displaystyle{ 7}\) ) i \(\displaystyle{ 2222}\) na końcu.
Stąd szukana reszta jest taka sama jak reszta z dzielenia przez \(\displaystyle{ 7}\) liczby \(\displaystyle{ 220}\).

Czyli nie ma w takich przypadkach redukowania modulo dla poteg?

Wpierw musisz mieć potęgę.
\(\displaystyle{ 222...22= \frac{2}{9} \left( 10 ^{100}-1 \right)}\)
Możesz spróbować z tym powalczyć. Inny warunek podzielności przez \(\displaystyle{ 7}\) dotyczy sumy:
\(\displaystyle{ a _{10^0}+2a _{10^1}+3a _{10^2}-a _{10^3}-2a _{10^4}-3a _{10^5}+\\
+a _{10^6}+2a _{10^7}+3a _{10^8}-a _{10^9}-2a _{10^{10}}-3a _{10^{11}}+\\
+a _{10^{12}}+2a _{10^{13}}+3a _{10^{14}}-a _{10^{15}}-....}\)
gdzie \(\displaystyle{ a _{10 ^{i} }}\) to cyfry z miejsca \(\displaystyle{ 10^i}\) w liczbie.
Tu przy jednakowych cyfrach składniki sumy się redukują aż zostanie:
\(\displaystyle{ 2+2 \cdot 2+3 \cdot 2-2=10}\)
Liczba nie jest podzielna przez \(\displaystyle{ 7}\). Jednak gdyby odjąć od niej \(\displaystyle{ 3}\) to podzielna już będzie. Stąd szukana reszta to \(\displaystyle{ 3}\).