Coś do dużej potęgi modulo liczba

[VillagerMTV]

Witam!
Mam problem z zadaniami typu:
Oblicz:
\(\displaystyle{ 18^{4567}\pmod{13}.}\)
Pomoże ktoś jakąś wskazówką?

[kristoffwp]

Wszystko modulo 13.
\(\displaystyle{ 18\equiv 5 \\ 18^{4566}\equiv 5^{4566}\equiv (5^2)^{2283}\equiv 25^{2283}\equiv (-1)^{2283} =-1}\)
\(\displaystyle{ 18^{4566}\cdot 18\equiv -1\cdot 18=-18\equiv 8}\)

[VillagerMTV]

Czyli jak bym maił taki przykład:
\(\displaystyle{ 55^{1876}\pmod{12}}\) to mam zrobić tak:
\(\displaystyle{ 55\pmod{12}=7}\)
\(\displaystyle{ 1876\pmod{12}=4}\)
\(\displaystyle{ 7^{4}\pmod {12}=11^{2}\pmod{12}=1}\)?

[kristoffwp]

To nie przypomina tego, co pokazałem.
\(\displaystyle{ 55\equiv 7\\55^2\equiv 7^2\equiv 1\\ 55^{1876}\equiv 1^{938}=1.\\}\)

Wyszło nam tyle samo. Za późno jak dla mnie, żeby twoje rozumowanie analizować. Ja tego nie rozumiem.

[VillagerMTV]

Nie wygląda, bo trochę inaczej to rozpisałem.
Ogólnie to na początku liczbę podzieliłem \(\displaystyle{ modulo 12}\), później wykładnik.
Z liczby zostało \(\displaystyle{ 7}\), z wykładnika \(\displaystyle{ 4}\).
A więc liczba uprościła się do \(\displaystyle{ 7^4(modulo 12)}\)
Podniosłem do \(\displaystyle{ 2}\) i podzieliłem przez \(\displaystyle{ 12}\). Zostało \(\displaystyle{ 11^{2} (modulo 12)}\). A to już na palcach wyszło, że jest to \(\displaystyle{ 1}\).

Takie rozumowanie jest poprawne czy to było szczęście?

[Ponewor]

To był czysty fart. Nie jest prawdziwe twierdzenie \(\displaystyle{ b \equiv c \pmod{d} \Rightarrow a^{b} \equiv a^{c} \pmod{d}}\)
Dla kontrprzykładu weźmy \(\displaystyle{ a=2, \ b=1 , \ c=4, \ d=3}\). Wówczas \(\displaystyle{ b\equiv 4 \pmod{3}}\), ale \(\displaystyle{ 2^{1} \not\equiv 2^{4} \pmod{3}}\)

[Premislav]

Ja tylko może wspomnę, że przy takich cudach pomocne okazuje się często Twierdzenie Eulera.

[VillagerMTV]

Dziękuję za pomoc!

-- 15 kwi 2014, o 13:46 --

A jak wyliczyć takie coś:
\(\displaystyle{ 2017^{2018^{2019}} \pmod{10}}\)?

\(\displaystyle{ 2017 \equiv 7 \pmod{10}}\)
\(\displaystyle{ 2018 \equiv 8 \pmod{10}}\)

\(\displaystyle{ 8^{2018} \cdot 8 \equiv 4^{1009} \pmod{10}}\) Czyli potęga będzie parzysta?
\(\displaystyle{ 7^{2} =-1 \pmod{10}}\) Czyli całość to \(\displaystyle{ 1}\) ?

[Ponewor]

To rozwiązanie jest błędne.

\(\displaystyle{ 2017 \equiv 7 \pmod{10}}\)
\(\displaystyle{ 7^{4} \equiv 1 \pmod{10}}\)
Wystarczy więc policzyć \(\displaystyle{ 2018^{2019} \mod 4 =0}\)
Zatem \(\displaystyle{ 7^{2018^{2019}} \equiv 7^{4k} \equiv \left(7^{4}\right)^{k}\equiv 1^{k} \equiv 1 \pmod{10}}\)