Witam uczę się właśnie kongruencji i mam problem z tymi przykładami.
Wyznacz dwie ostatnie cyfry liczby.
a) \(\displaystyle{ 6 ^{10}}\)
b) \(\displaystyle{ 13^{13}}\)
Jeśli nie obejdzie się bez Funkcja Carmichaela czy też Funkcji Eulera to jak byście mogli pokazać użycie ich na właśnie tych przykładach.-- 1 lip 2018, o 21:58 --dodam że potrafię to zrobić bez kongruencji ale chcą ją dobrze przećwiczyć.
Wyznacz dwie ostatnie cyfry liczby.Kongruencja
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Wyznacz dwie ostatnie cyfry liczby.Kongruencja
Szczęść Boże.
a)
\(\displaystyle{ 6^4=1296\equiv -4\pmod{100}\\ (6^4)^2\equiv 16\pmod{100}\\ 6^{10}=(6^4)^2\cdot 6^2\equiv 16\cdot 36\pmod{100}}\)
czyli w końcu \(\displaystyle{ 6^{10}\equiv 76\pmod{100}}\),
stąd te dwie ostatnie cyfry wyglądają tak: \(\displaystyle{ 76}\).
b)
\(\displaystyle{ 13\equiv 1\pmod{4}}\), toteż \(\displaystyle{ 13^{13}\equiv 1\pmod{4}}\).
Ponadto łatwo obliczyć w pamięci, że \(\displaystyle{ 13^6\equiv 9\pmod{25}}\), a więc \(\displaystyle{ 13^{12}=(13^6)^2\equiv 6\pmod{25}}\) oraz
\(\displaystyle{ 13^{13}=(13^6)^2\cdot 13\equiv 3\pmod{25}}\).
Zatem liczba \(\displaystyle{ 13^{13}\pmod{100}}\)
jest rozwiązaniem układu kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 1\pmod{4}\\ x\equiv 3\pmod{25} \end{cases}}\)
Z chińskiego twierdzenia o resztach ten układ ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{100}}\) i jak nam się nie chce używać tego algorytmu powiązanego z rozszerzonym algorytmem Euklidesa, to można zgadnąć rozwiązanie: \(\displaystyle{ x\equiv 53\pmod{100}}\).
Stąd te dwie ostatnie cyfry liczby \(\displaystyle{ 13^{13}}\) wyglądają tak: \(\displaystyle{ 53}\).
Z Bogiem, KW
a)
\(\displaystyle{ 6^4=1296\equiv -4\pmod{100}\\ (6^4)^2\equiv 16\pmod{100}\\ 6^{10}=(6^4)^2\cdot 6^2\equiv 16\cdot 36\pmod{100}}\)
czyli w końcu \(\displaystyle{ 6^{10}\equiv 76\pmod{100}}\),
stąd te dwie ostatnie cyfry wyglądają tak: \(\displaystyle{ 76}\).
b)
\(\displaystyle{ 13\equiv 1\pmod{4}}\), toteż \(\displaystyle{ 13^{13}\equiv 1\pmod{4}}\).
Ponadto łatwo obliczyć w pamięci, że \(\displaystyle{ 13^6\equiv 9\pmod{25}}\), a więc \(\displaystyle{ 13^{12}=(13^6)^2\equiv 6\pmod{25}}\) oraz
\(\displaystyle{ 13^{13}=(13^6)^2\cdot 13\equiv 3\pmod{25}}\).
Zatem liczba \(\displaystyle{ 13^{13}\pmod{100}}\)
jest rozwiązaniem układu kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 1\pmod{4}\\ x\equiv 3\pmod{25} \end{cases}}\)
Z chińskiego twierdzenia o resztach ten układ ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{100}}\) i jak nam się nie chce używać tego algorytmu powiązanego z rozszerzonym algorytmem Euklidesa, to można zgadnąć rozwiązanie: \(\displaystyle{ x\equiv 53\pmod{100}}\).
Stąd te dwie ostatnie cyfry liczby \(\displaystyle{ 13^{13}}\) wyglądają tak: \(\displaystyle{ 53}\).
Z Bogiem, KW
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy