reszta z dzielenia

wiosna · Post autor: **wiosna** » 21 lut 2009, o 14:24

Znajdź resztę z dzielenia \(\displaystyle{ 9^{8^{7}}}\) przez \(\displaystyle{ 37}\).

grzesiiek · Post autor: **grzesiiek** » 21 lut 2009, o 14:45

wydaje mi sie ze reszta z dzielenia bedzie \(\displaystyle{ \frac{9}{37}}\)

max · Post autor: **max** » 21 lut 2009, o 15:06

Z małego tw Fermata \(\displaystyle{ 9^{36}\equiv 1\pmod{37},}\) bo \(\displaystyle{ 37}\) pierwsze i nie dzieli \(\displaystyle{ 9.}\)

Dalej szukamy takiego \(\displaystyle{ y\in \{0,1,\ldots, 35\},}\) że:
\(\displaystyle{ 8^{7}\equiv y \pmod{36}}\)
Kongruencja ta jest równoważna podzielności \(\displaystyle{ 36| 8^{7} - y,}\) w szczególności \(\displaystyle{ 4|8^{7} - y,}\) więc \(\displaystyle{ y\equiv 8^{7} \equiv 0\pmod{4},}\) stąd \(\displaystyle{ y =4x,}\) dla pewnego \(\displaystyle{ x\in\mathbb{Z}.}\)
Ale \(\displaystyle{ 8^{7} - 4x = 36k \iff 2\cdot 8^{6} - x = 9k,}\) czyli nasz warunek jest równoważny kongruencji:
\(\displaystyle{ 2\cdot 8^{6} \equiv x \pmod{9}}\)
z tw Eulera \(\displaystyle{ 8^{6}\equiv 1\pmod{9},}\) bo \(\displaystyle{ \varphi(9) = 6}\) oraz \(\displaystyle{ 8,9}\) są względnie pierwsze.
Stąd też \(\displaystyle{ x \equiv 2\pmod{9},}\) czyli \(\displaystyle{ x - 2 = 9l}\) co jest równoważne \(\displaystyle{ 4x - 8 = 36l,}\) a więc \(\displaystyle{ y = 4x \equiv 8\pmod{36}.}\)

Ostatecznie:
\(\displaystyle{ 9^{8^{7}}= 9^{36k + 8}\equiv 9^{8} = 81^{4} \equiv 7^{4} = 49^{2}\equiv 12^{2} \equiv -4 \equiv 33\pmod{37}}\)

Xitami · Post autor: **Xitami** » 21 lut 2009, o 23:12

\(\displaystyle{ 9^{8^7}\equiv7\ (mod\ 37)}\)
Do sprawdzenia wystarczy windowsowy kalkulator

meninio · Post autor: **meninio** » 21 lut 2009, o 23:29

Mój windowsowy kalkulator nie umie tego policzyć

Maciej87 · Post autor: **Maciej87** » 22 lut 2009, o 00:03

Xitami pisze:\(\displaystyle{ 9^{8^7}\equiv7\ (mod\ 37)}\)
Do sprawdzenia wystarczy windowsowy kalkulator

Dobrze umieć liczyć proste rzeczy ręcznie a potem posługiwać się programami.
Odpowiedzią jest \(\displaystyle{ 33}\) i kropka.
To co ty policzyłeś to \(\displaystyle{ \left(9^8\right)^7=9^{8\cdot 7}}\). My chcemy liczyć \(\displaystyle{ 9^{8^{7}}}\)

Xitami · Post autor: **Xitami** » 22 lut 2009, o 01:54

Dziękuję Macieju za naprostowanie
\(\displaystyle{ \left(9^8\right)^7}\) różni się nieco od \(\displaystyle{ 9^{(8^7)}}\)

\(\displaystyle{ 8^7=2^{21}}\)
no to liczę na kalkulatorze
[3] [7] [MS]
[9]
21 razy powtarzam [x^2][MOD][MR][=]
wychodzi 33

Maciej87 · Post autor: **Maciej87** » 22 lut 2009, o 10:09

Teraz jest fajnie.
A więc, podsumowując mamy twierdzenie:
ten problem da się rozwiązać Windowsowym kalkulatorem.