Cześć nie do końca wiem jak mam rozwiązać to zadanie:
Wykorzystując twierdzenie Eulera oraz Chińskie twierdzenie o resztach wyznacz resztę z dzielenia \(\displaystyle{ 11^{111}}\) przez \(\displaystyle{ 323}\).
Moje rozwiązanie
\(\displaystyle{ 11^{111}\equiv A\pmod{323}}\)
\(\displaystyle{ 323=29 \cdot 11+4\\
11=2 \cdot 4+3\\
4=1 \cdot 3+1\\
3=3 \cdot 1+0\\
NWD(323,11)=1}\)
\(\displaystyle{ \phi(323)=\phi(17)\phi(19)=16 \cdot 18=288}\)
Czyli
\(\displaystyle{ 11^{288}\equiv 1\pmod{323}}\)
I teraz nie wiem jak dalej liczyć bo nie wiem jak z \(\displaystyle{ 288}\) uzyskać aby potęga była \(\displaystyle{ 111}\). I w ogóle nie wiem kiedy i jak wykorzystać to Chińskie twierdzenie o resztach.
proszę o pomoc
Twierdzenie Eulera i Chińskie twierdzenie o resztach
-
- Użytkownik
- Posty: 2
- Rejestracja: 20 cze 2018, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 1 raz
Twierdzenie Eulera i Chińskie twierdzenie o resztach
Ostatnio zmieniony 20 cze 2018, o 16:42 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
- 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: Twierdzenie Eulera i Chińskie twierdzenie o resztach
No tak to nie pójdzie, trzeba oddzielnie wyznaczyć resztę z dzielenia
\(\displaystyle{ 11^{111}}\) przez \(\displaystyle{ 17}\) i przez \(\displaystyle{ 19}\), a następnie skorzystać z chińskiego twierdzenia o resztach.
Mamy \(\displaystyle{ \phi(17)=16}\) i \(\displaystyle{ 111=16\cdot 7-1}\), więc
\(\displaystyle{ 11^{111}=(11^{16})^711^{-1}\equiv 11^{-1}\pmod{17}}\)
na mocy twierdzenia Eulera,
natomiast stosując rozszerzony algorytm Euklidesa do \(\displaystyle{ 11}\) i \(\displaystyle{ 17}\), możemy łatwo wyliczyć, że w \(\displaystyle{ \ZZ_{17}}\) jest \(\displaystyle{ 11^{-1}=14}\), zatem
ostatecznie \(\displaystyle{ 11^{111}\equiv 14\pmod{17}}\).
Podobnie robimy z \(\displaystyle{ 19}\), mamy \(\displaystyle{ \phi(19)=18}\) oraz
\(\displaystyle{ 111=6\cdot 18+3}\), tj.
\(\displaystyle{ 11^{111}=(11^{18})^6\cdot 11^3\equiv 11^3\pmod{19}}\)
również na mocy tw. Eulera.
No a \(\displaystyle{ 11^3=1331=950+380+1\equiv 1\pmod{19}}\),
stąd \(\displaystyle{ 11^{111}\equiv 1\pmod{19}}\).
Z chińskiego twierdzenia o resztach mamy, że
układ kongruencji
\(\displaystyle{ \begin{cases} x\equiv 14\pmod{17}\\ x\equiv 1\pmod{19} \end{cases}}\)
ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{323}}\).
Nie chce mi się tego rozpisywać, po prostu się naucz jednego z algorytmów wyznaczania takowego rozwiązania (np. na wiki jest: ... o_resztach), tu nie ma żadnego kreatywnego pomysłu, dość łatwo wyznaczyć rozwiązanie, \(\displaystyle{ 286}\), czyli ostatecznie
\(\displaystyle{ 11^{111}\equiv 286\pmod{323}}\)
\(\displaystyle{ 11^{111}}\) przez \(\displaystyle{ 17}\) i przez \(\displaystyle{ 19}\), a następnie skorzystać z chińskiego twierdzenia o resztach.
Mamy \(\displaystyle{ \phi(17)=16}\) i \(\displaystyle{ 111=16\cdot 7-1}\), więc
\(\displaystyle{ 11^{111}=(11^{16})^711^{-1}\equiv 11^{-1}\pmod{17}}\)
na mocy twierdzenia Eulera,
natomiast stosując rozszerzony algorytm Euklidesa do \(\displaystyle{ 11}\) i \(\displaystyle{ 17}\), możemy łatwo wyliczyć, że w \(\displaystyle{ \ZZ_{17}}\) jest \(\displaystyle{ 11^{-1}=14}\), zatem
ostatecznie \(\displaystyle{ 11^{111}\equiv 14\pmod{17}}\).
Podobnie robimy z \(\displaystyle{ 19}\), mamy \(\displaystyle{ \phi(19)=18}\) oraz
\(\displaystyle{ 111=6\cdot 18+3}\), tj.
\(\displaystyle{ 11^{111}=(11^{18})^6\cdot 11^3\equiv 11^3\pmod{19}}\)
również na mocy tw. Eulera.
No a \(\displaystyle{ 11^3=1331=950+380+1\equiv 1\pmod{19}}\),
stąd \(\displaystyle{ 11^{111}\equiv 1\pmod{19}}\).
Z chińskiego twierdzenia o resztach mamy, że
układ kongruencji
\(\displaystyle{ \begin{cases} x\equiv 14\pmod{17}\\ x\equiv 1\pmod{19} \end{cases}}\)
ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{323}}\).
Nie chce mi się tego rozpisywać, po prostu się naucz jednego z algorytmów wyznaczania takowego rozwiązania (np. na wiki jest: ... o_resztach), tu nie ma żadnego kreatywnego pomysłu, dość łatwo wyznaczyć rozwiązanie, \(\displaystyle{ 286}\), czyli ostatecznie
\(\displaystyle{ 11^{111}\equiv 286\pmod{323}}\)