Wyznacz resztę dzielenia liczby całkowitej przez 73

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Wyznacz resztę dzielenia liczby całkowitej przez 73

Post autor: matinf »

Znajdź resztę z dzielenia liczby całkowitej \(\displaystyle{ a}\) przez \(\displaystyle{ 73}\)wiedząc,
że \(\displaystyle{ a^{100} \equiv 2\pmod{73}}\) oraz \(\displaystyle{ a ^{101} \equiv 69 \pmod{73}}\).
Ostatnio zmieniony 25 maja 2014, o 01:19 przez , łącznie zmieniany 1 raz.
Powód: Temat umieszczony w złym dziale. Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
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

Wyznacz resztę dzielenia liczby całkowitej przez 73

Post autor: Premislav »

\(\displaystyle{ 73}\) jest liczbą pierwszą. Od razu widać (warunki), że \(\displaystyle{ 73}\) nie dzieli \(\displaystyle{ a}\), zatem z małego twierdzenia Fermata \(\displaystyle{ a ^{72} \equiv1\pmod{73}}\). Jeśli ktoś nie lubi dużych wykładników i te wydają mu się duże, może to więc zredukować do \(\displaystyle{ a ^{28}\equiv 2\pmod{73}}\) i \(\displaystyle{ a^{29}\equiv69\pmod{73}}\). Tę pierwszą kongruencję możemy pomnożyć stronami przez \(\displaystyle{ a}\) i mamy koniunkcję \(\displaystyle{ a ^{29}\equiv 2a\pmod{73} \wedge a^{29}\equiv69\pmod{73}}\). Stąd oczywiście \(\displaystyle{ 2a\equiv69\pmod{73}}\)(*). Korzystając z rozszerzonego algorytmu Euklidesa, znajdujesz takie \(\displaystyle{ m}\), że \(\displaystyle{ 2m\equiv1\pmod{73}}\) (istnieje, bo \(\displaystyle{ (2,73)=1}\)), mnożysz przez nie [przez to \(\displaystyle{ m}\)] stronami kongruencję (*), redukujesz po prawej stronie wielokrotności \(\displaystyle{ 73}\) i masz wynik.
ODPOWIEDZ