Reszty z dzielenia

[Bran]

Zadanie: Udowodnij, że reszta z dzielenia przez \(\displaystyle{ 10}\) liczby \(\displaystyle{ 33^{100}}\) jest taka sama jak reszta z dzielenia
przez \(\displaystyle{ 10}\) liczby \(\displaystyle{ 3^{100}}\)


Rozwiążę zadanie na dwa sposoby.
Sposób I

Zauważmy, że
\(\displaystyle{ 33 \equiv 3 (\mbox{mod } 10)}\) po podniesieniu obu stron do potęgi 100 otrzymujemy:

\(\displaystyle{ 33^{100} \equiv 3^{100} (\mbox{mod } 10)}\)
A to oznacza, że liczby te podzielone przez \(\displaystyle{ 10}\) mają taką samą resztę, a to dowodzi tezy.


Sposób II
Funkcja Eulera \(\displaystyle{ \phi(10) = 10 \left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{5}\right) = 4}\), ponadto \(\displaystyle{ \NWD(3, 10) = 1 \wedge \NWD(10, 33) = 1}\)

Więc z twierdzenia Eulera:
\(\displaystyle{ 3^4 \equiv 1 (\mbox{mod } 10)}\) podnieśmy obie strony kongruencji do potęgi \(\displaystyle{ 25}\)

\(\displaystyle{ 3^{100} \equiv 1 (\mbox{mod } 10)}\)

Z drugiej strony
\(\displaystyle{ 33^4 \equiv 1 (\mbox{mod } 10)}\) podnieśmy obie strony kongruencji do potęgi \(\displaystyle{ 25}\)

\(\displaystyle{ 33^{100} \equiv 1 (\mbox{mod } 10)}\)

W obydwu przypadkach reszta jest taka sama i wynosi \(\displaystyle{ 1}\), co kończy dowód.

Jest dobrze?

[Premislav]

Obydwa rozwiązania są poprawne, pozdrawiam cieplutko z rodzinką. Można również nie korzystać z kongruencji, tylko rozwinąć ze wzoru na różnicę \(\displaystyle{ n}\)-tych potęg
\(\displaystyle{ 33^{100}-3^{100}=30\cdot \sum_{i=0}^{99}33^{99-i}\cdot 3^{i}=\red{10}\cdot 3\sum_{i=0}^{99}33^{99-i}\cdot 3^{i}}\)
co dowodzi, że różnica tych liczb dzieli się przez dziesięć, ale skorzystanie z kongruencji jest zgrabniejsze.