Matematyka.pl

Poszukuje materiałów, zależności, wzorów które pozwoliłyby mi rozwiązać zadania podobne do poniższego.

Wykorzystujac algorytm Euklidesa oblicz.
\(\displaystyle{
20^{128}\mod 1323 \\
55^{5}\mod 504
}\)

Nie widzę, by algorytm Euklidesa miał tu coś do rzeczy, być może jest to jakaś metoda rozwiązania za pomocą algorytmu Euklidesa (rozszerzonego?), której w tej chwili nie kojarzę.
Mamy
\(\displaystyle{ 1323=27\cdot 49 }\) i \(\displaystyle{ \NWD(27, 49)=1}\), można od tego zacząć.
Obliczymy wartość funkcji Eulera dla \(\displaystyle{ 27}\) i \(\displaystyle{ 49}\) zgodnie ze znanymi wzorkami:
\(\displaystyle{ \varphi(27)=\varphi\left(3^{3}\right)=(3-1)\cdot 3^{3-1}=18, \varphi(49)=\varphi\left(7^{2}\right)=(7-1)\cdot 7^{2-1}=42}\)
Na mocy twierdzenia Eulera mamy więc
\(\displaystyle{ 20^{18}\equiv 1\pmod{27}}\) oraz \(\displaystyle{ 20^{42}\equiv 1\pmod{49}}\), stąd przez banalną indukcję dostajemy, że dla dowolnego \(\displaystyle{ k\in \NN^{+}, \ 20^{18k}\equiv 1\pmod{27}, \ 20^{42k}\equiv 1\pmod{49}}\).
Odnotujmy teraz, że \(\displaystyle{ 128=126+2}\), a dzielnikami liczby \(\displaystyle{ 126=2\cdot 3^{2}\cdot 7}\) są zarówno \(\displaystyle{ 18}\), jak i \(\displaystyle{ 42}\).
Otrzymujemy zatem (tak naprawdę przemyca się tu w pewnej formie chińskie twierdzenie o resztach)
\(\displaystyle{ 20^{126}\equiv 1\pmod{1323}\\20^{128}=20^{126}\cdot 20^{2}\equiv 20^{2}\pmod{1323}}\)
czyli podsumowując, \(\displaystyle{ 20^{128}\equiv 400\pmod{1323}}\).

Dodano po 16 minutach :
W tym drugim można po prostu podnieść do potęgi na pałę (na przykład korzystając ze wzorów skróconego mnożenia) i obliczyć na chama pod kreską. Jeśli jednak myślisz o bardziej kształcącym sposobie, to można zauważyć, że \(\displaystyle{ 504=7\cdot 8\cdot 9}\), a ponadto:
\(\displaystyle{ 55\equiv 1\pmod{9}, \ 55^{5}\equiv 1\pmod{9}\\55\equiv -1\pmod{7}, \ 55^{5}\equiv (-1)^{5}\pmod{7}, \ 55^{5}\equiv 6\pmod{7}\\55\equiv -1\pmod{8}, \ 55^{5}\equiv (-1)^{5}\pmod{8}, \ 55^{5}\equiv 7\pmod{8}}\)
czyli szukamy rozwiązania układu kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 6\pmod{7}\\x\equiv 7\pmod{8}\\x\equiv 1\pmod{9}\end{cases}}\)
w \(\displaystyle{ \ZZ_{504}}\). Takie rozwiązanie będzie jedyne na mocy chińskiego twierdzenia o resztach i możesz skorzystać teraz z metody generowania rozwiązania tu opisanej:

Dodano po 1 minucie 35 sekundach:
Ogólnie przydatne zagadnienia w takich zadaniach to twierdzenie Eulera (i jego szczególny przypadek, czyli małe twierdzenie Fermata), chińskie twierdzenie o resztach, wzory skróconego mnożenia, cechy podzielności przez małe liczby.

Prowadzący podał takie rozwiązanie pierwszego zadania.
\(\displaystyle{
1323 = 3^2\cdot 7^2\\
\varphi(1323)=\varphi(3^3)\varphi(7^2)=2\cdot 3^2\cdot 6\cdot 7=756 \\
\lambda(1323)=NWW(\lambda(3^3),\lambda(7^2)) = NWW(2\cdot 3^2,6\cdot 7 )= 126 \\
20^{128} \mod 1323 = 20^{128\mod 126}\mod 1323 = 20^2 \mod 1323 = 400
}\)
Jesteś w stanie to wytłumaczyć, bo twoje rozwiazanie jest dosc obszerne i trudne.

2)

\(\displaystyle{ 55^5 \mod 504 =(55^2)^2 \cdot 55 \mod 504 =(6 \cdot 504+1)^2 \cdot 55 \mod 504 \equiv 1 \cdot 55 \mod 504 =55}\)

caballo795 pisze:Jesteś w stanie to wytłumaczyć, bo twoje rozwiazanie jest dosc obszerne i trudne.

Wybacz, ale z tego śmiechłem hardo (bez złośliwości). Przecież to jest praktycznie to samo, co ja napisałem, tylko bez użycia języka polskiego, a jedynie symboli. Obszerność bierze się z tego, że używam zdań w języku polskim, a co do trudności, to nie wiem, skąd taka opinia, z tego, co patrzę, to prowadzący tez używa funkcji Eulera i twierdzenia Eulera.