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
Reszta z dzielenia - potęga
-
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Reszta z dzielenia - potęga
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.
Jeśli nadal nie będziesz wiedział, co z tym zrobić - pisz.
Pozdrawiam.
-
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Reszta z dzielenia - potęga
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.
Btw, nie uważasz, że lepiej skorzystać jednak z MTF (TE), czyli z tego, że \(\displaystyle{ 5^{16}\equiv 1 \mod 17}\)?
Pozdrawiam.
- smigol
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
Reszta z dzielenia - potęga
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.
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.
Reszta z dzielenia - potęga
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...
\(\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...
-
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Reszta z dzielenia - potęga
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.
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.