reszta z dzielenia - kongruencje

[magda87]

Proszę o pomoc w rozwiązaniu zadania:

Znajdź resztę z dzielenia \(\displaystyle{ 2 ^{1000000}}\) przez \(\displaystyle{ 77}\). Nie wiem jak się za to zabrać:(

[Qń]

Skorzystaj z twierdzenia Eulera:
\(\displaystyle{ 2^{\phi(77)}\equiv 1 \pmod{77}}\)

Q.

[magda87]

Skorzystałam z tw. Euklidesa i wyszło mi tak:

\(\displaystyle{ \varphi\left( 77\right) = 76\\ 2 ^{\left(77 \right) }\equiv 1\left( mod77\right)\\2 ^{76}\equiv 1\left( mod77\right) \\\left( 2 ^{76} \right) ^{13157}\equiv 1 ^{13157} \left( mod77\right)\\ 2 ^{999932} \equiv 2^{68} \cdot 1\left( mod77\right) \\ 2 ^{999932} \equiv 2^{68} \left( mod77\right)}\)

[Qń]

Skorzystałam z tw. Euklidesa

Chyba jednak z twierdzenia Eulera.

\(\displaystyle{ \varphi\left( 77\right) = 76}\)

To nieprawda.

Q.

[magda87]

No tak moja pomyłka, chodziło o tw. Eulera. Mialam na wykładzie wzór \(\displaystyle{ \varphi\left( m\right) = m-1}\) i z niego skorzystałam, dlaczego to jest zle?

[Qń]

Mialam na wykładzie wzór \(\displaystyle{ \varphi\left( m\right) = m-1}\)

Ten wzór działa tylko dla liczb pierwszych, w ogólności jest inny. Przeczytaj notatki z wykładu uważniej.

Q.

[magda87]

a no tak, ja zastosowalam ten dla pierwszych a ogolnie to powinnam skorzystać z tego :
\(\displaystyle{ \varphi\left( m\right) = m \cdot \left( 1- \frac{1}{p _{1}} \right) \cdot \left( 1- \frac{1}{p _{2}} \right)\cdot \left( 1- \frac{1}{p _{n}} \right)}\)
według tego wzoru \(\displaystyle{ \varphi\left( 77\right) = 60}\)
a dalej wyliczam tak samo jak poprzednio?

[Qń]

Zgadza się - mamy wtedy:
\(\displaystyle{ 2^{1000000} \equiv 2^{40}\pmod{77}}\)
i wystarczy na piechotę policzyć do czego przystaje \(\displaystyle{ 2^{40}}\), zaczynając na przykład od obserwacji:
\(\displaystyle{ 2^{40}=(2^{10})^4=1024^4 = (13\cdot 77 +23)^4}\)

Q.