Działania modularne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Kate2410

Działania modularne

Post autor: Kate2410 »

Sprawdzić czy
\(\displaystyle{ 5 ^{70}=2\pmod{71} }\)
Z jakich własności trzeba tu skorzystać?
Ostatnio zmieniony 21 lis 2019, o 01:49 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Działania modularne

Post autor: Premislav »

\(\displaystyle{ 71}\) jest liczbą pierwszą i \(\displaystyle{ \NWD(5, 71)=1}\), więc z małego twierdzenia Fermata mamy \(\displaystyle{ 5^{70}\equiv 1\pmod{71}}\).
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Działania modularne

Post autor: Janusz Tracz »

Można również zauważyć, że \(\displaystyle{ 5^5\equiv 1\pmod{71}}\) a zatem podnosząc kongruencję stronami do potęgi \(\displaystyle{ n}\) (formalnie można to indukcją pokazać) dostajemy, że dla każdego \(\displaystyle{ n\in\NN}\) zachodzi \(\displaystyle{ 5^{5n}\equiv 1\pmod{71}}\). Stąd natychmiastowy wniosek, że nieprawdą kongruencja z zadania.
ODPOWIEDZ