Twierdzenie Eulera i Chińskie twierdzenie o resztach

[Rokoch]

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

[Premislav]

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}}\)