Algorytm szukania modulo - wytłumaczenie zasady działania

[krzysiek852]

Cześć,

Załóżmy, że chcemy wyznaczyć \(\displaystyle{ 12345\pmod{100}}\).
Skorzystamy z następującego algorytmu:

\(\displaystyle{ \begin{array}{l}
reszta = 1\pmod{100} \\
reszta = (reszta*10 + 2)\pmod{100}\\
reszta = (reszta*10 + 3)\pmod{100} \\
reszta =(reszta*10 + 4)\pmod{100}\\
reszta= (reszta*10 + 5)\pmod{100}\\
reszta = 45\\
\end{array}}\)

Sama idea jest jasna: bierzemy pierwszą cyfrę i z niej resztę z dzielenia przez sto. W kolejnym kroku otrzymaną wcześniej resztę mnożymy przez dziesięć , dodajemy kolejną cyfrę i wyznaczamy resztę z dzielenia przez sto, itd.
W jaki sposób ten algorytm działa? Dlaczego na początku bierzemy pojedynczą cyfrę \(\displaystyle{ 1}\), mimo to, że jest to cyfra dziesiątek tysięcy i wyznaczamy jej resztę, a nie startujemy na przykład od \(\displaystyle{ 5 }\)?