Witam, mam lekkie problemy z jednym zadankiem:
Znaleźć resztę z dzielenia liczby całkowitej \(\displaystyle{ a}\) przez 19, jeżeli wiadomo, że liczba \(\displaystyle{ a ^{17}}\) ma resztę 12 z dzielenia przez 19.
dzięki, jakby ktoś szkic rozwiązania dał, z czego skorzystać przy robieniu, albo krok po kroku zrobił
Kongruencje, reszta z dzielenia
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Kongruencje, reszta z dzielenia
Z treści zadania mamy, że \(\displaystyle{ a^{17}\equiv 12 \ (mod19)}\)
Natomiast z małego tw. Fermata mamy:
\(\displaystyle{ a^{18}=a^{19-1}\equiv 1 \ (mod19)}\)
Zatem otrzymujemy \(\displaystyle{ a^{18}=a^{17}*a\equiv 12a\equiv 1 \ (mod19)}\)
Po sprawdzeniu otrzymamy, że \(\displaystyle{ a\equiv 4 \ (mod19)}\)
Natomiast z małego tw. Fermata mamy:
\(\displaystyle{ a^{18}=a^{19-1}\equiv 1 \ (mod19)}\)
Zatem otrzymujemy \(\displaystyle{ a^{18}=a^{17}*a\equiv 12a\equiv 1 \ (mod19)}\)
Po sprawdzeniu otrzymamy, że \(\displaystyle{ a\equiv 4 \ (mod19)}\)
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Kongruencje, reszta z dzielenia
Raczej \(\displaystyle{ a \equiv 8 \ (mod \ 19)}\)polskimisiek pisze:Po sprawdzeniu otrzymamy, że \(\displaystyle{ a\equiv 4 \ (mod19)}\)
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy