Kongruencje, reszta z dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
MorRav
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 6 gru 2007, o 22:25
Płeć: Mężczyzna
Lokalizacja: Białystok

Kongruencje, reszta z dzielenia

Post autor: MorRav »

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ł
Piotr Rutkowski
Użytkownik
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

Post autor: Piotr Rutkowski »

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)}\)
Awatar użytkownika
Sylwek
Użytkownik
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

Post autor: Sylwek »

polskimisiek pisze:Po sprawdzeniu otrzymamy, że \(\displaystyle{ a\equiv 4 \ (mod19)}\)
Raczej \(\displaystyle{ a \equiv 8 \ (mod \ 19)}\)
Piotr Rutkowski
Użytkownik
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

Post autor: Piotr Rutkowski »

Racja, oczywiście
ODPOWIEDZ