Reszta z dzielenia - potęga

yaszko · Post autor: **yaszko** » 10 lut 2010, o 17:00

Witam wszystkich.
Jak wyznaczyć resztę z dzielenia \(\displaystyle{ 5^{2009}}\) przez \(\displaystyle{ 17}\) ?
Proszę o metodę wraz z rozwiązaniem bo siedzę nad tym i nie mogę nic wymyślić:)
Pozdrawiam

BettyBoo · Post autor: **BettyBoo** » 10 lut 2010, o 17:28

To może zajrzyj do notatek pod hasło "Małe Twierdzenie Fermata" lub ewentualnie "Twierdzenie Eulera".

Jeśli nadal nie będziesz wiedział, co z tym zrobić - pisz.

Pozdrawiam.

smigol · Post autor: **smigol** » 10 lut 2010, o 17:35

MTF jak MTF, ale twierdzenie Euklidesa do czegoś takiego? -_-

hint:
\(\displaystyle{ 5^4 \equiv 4 \ (mod \ 17)}\)

BettyBoo · Post autor: **BettyBoo** » 10 lut 2010, o 17:46

smigol, a kto tutaj - poza Tobą - wspomina o twierdzeniu Euklidesa?

Btw, nie uważasz, że lepiej skorzystać jednak z MTF (TE), czyli z tego, że \(\displaystyle{ 5^{16}\equiv 1 \mod 17}\)?

Pozdrawiam.

smigol · Post autor: **smigol** » 10 lut 2010, o 17:49

Przepraszam za przejęzyczenie

Owszem, że uważam, bo jest szybciej i przyjemniej. Ale myślę, że takie zadania to się w szkole średniej na kółkach robi i niekoniecznie się zna MTF )

Pozdrawiam.

yaszko · Post autor: **yaszko** » 10 lut 2010, o 19:02

Robiłem tak już wcześniej:
\(\displaystyle{ 5^{16}=1(mod17)}\)
czyli:
\(\displaystyle{ 5^{16*125+9}=1(mod17)}\)
\(\displaystyle{ 5^{16*125}*5^9=5^{9}*1^{16*125}(mod17)}\)

wychodzi że reszta to \(\displaystyle{ 5^{9}}\) ale chyba nie...

BettyBoo · Post autor: **BettyBoo** » 10 lut 2010, o 19:08

Nie, wychodzi że reszta z dzielenia wyjściowej liczby przz 17 jest taka sama, jak reszta z dzielenia \(\displaystyle{ 5^9}\) przez 17.

No i początek dobrze, teraz trzeba to tylko obliczyć. Liczysz \(\displaystyle{ 5^2, 5^4, 5^8 \mod 17}\) więc odpowiedź to \(\displaystyle{ 5\cdot 5^8\mod 17 =...}\)

Pozdrawiam.

yaszko · Post autor: **yaszko** » 10 lut 2010, o 19:22

Dzięki wszystko wychodzi