potęgowanie modularne

[patricia__88]

Czy może mi ktoś dokładnie wyjaśnić, krok po kroku, jak obliczyć np.
a). \(\displaystyle{ 13^{101} \ mod \ 16}\)
b). \(\displaystyle{ 22^{2011} \ mod \ 13}\)
korzystając z twierdzenia Eulera, tzn.:
Dla dowolnych \(\displaystyle{ a,m\in\mathbb{N}}\), gdzie \(\displaystyle{ (a,m)=1}\) zachodzi: \(\displaystyle{ a^{\varphi(m)}=1 (mod \ m)}\)
Lub na jakimś innym własnym przykładnie.

[Vax]

a) Z twierdzenia Eulera \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\), więc:
\(\displaystyle{ 13^{101} \equiv (-3)^{101} \equiv -3^{101} \equiv -(3^{8})^{12}\cdot 3^{5} \equiv -3^5 \equiv -243 \equiv 13 \pmod{16}}\)

b) Z twierdzenia Eulera \(\displaystyle{ 9^{12} \equiv 1\pmod{13}}\), więc:

\(\displaystyle{ 22^{2011} \equiv 9^{2011} \equiv (9^{12})^{167}\cdot 9^{7} \equiv 9^7 \equiv 9\cdot 81^3 \equiv 9\cdot 3^3 \equiv 9\cdot 27 \equiv 9\pmod{13}}\)

[patricia__88]

a) Z twierdzenia Eulera \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\), więc:
\(\displaystyle{ 13^{101} \equiv (-3)^{101} \equiv -3^{101} \equiv -(3^{8})^{12}\cdot 3^{5} \equiv -3^5 \equiv -243 \equiv 13 \pmod{16}}\)

Rozumiem, że \(\displaystyle{ \varphi(16)=8}\), ale dlaczego liczymy \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\)?
Czy chodzi o to, że musimy dobrać takie \(\displaystyle{ a}\), żeby tw. Eulera było spełnione?
W takim razie dlaczego później mamy (-3)?

[Vax]

Dla dowolnego a takiego, że \(\displaystyle{ (a,m) = 1}\) mamy \(\displaystyle{ a^{\phi(m)} \equiv 1\pmod{m}}\), następnie zauważam, że \(\displaystyle{ 13 \equiv -3\pmod{16} \Rightarrow 13^{101} \equiv (-3)^{101} \equiv -3^{101} \pmod{16}}\)

Po prostu na mniejszych liczbach szybciej się liczy

[patricia__88]

Mam jeszcze pytanie do podpunktu b).
Czy nie możemy sobie wziąć \(\displaystyle{ a=2}\), bo przecież \(\displaystyle{ 2^{12}\equiv 1\pmod{13}}\) oraz \(\displaystyle{ (2,13)=1}\)

[MadJack]

Tylko \(\displaystyle{ 22}\) nie przystaje do \(\displaystyle{ 2}\) według modułu \(\displaystyle{ 13}\) tylko przystaje do \(\displaystyle{ 9}\), dlatego Vax wybrał tę liczbę.

[patricia__88]

ok dzieki wielkie juz wszystko rozumiem:)

[conradtbg]

Z twierdzenia Eulera \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\), więc:
\(\displaystyle{ 13^{101} \equiv (-3)^{101} \equiv -3^{101} \equiv -(3^{8})^{12}\cdot 3^{5} \equiv -3^5 \equiv -243 \equiv 13 \pmod{16}}\)

Może mi ktoś to objaśnić: \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\) ??? Wiem skąd się wzieło 8, ale nie wiem skąd jest ta liczba 3. Jak tą liczbę 3 obliczyć?

Rozumiem to \(\displaystyle{ 13^{101} \equiv (-3)^{101} \pmod{16}}\) że 13 przystaje do -3 (mod 13)

[Ponewor]

No tak, a potem skoro mamy nieparzysty wykładnik to
\(\displaystyle{ \left(-3\right)^{101}\equiv -\left(3^{101}\right)}\) skąd widać, że interesują nas potęgi trójki.

[conradtbg]

Nie rozumiem tego twierdzenia Eulera \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\). Skąd się wzieła 3 ? :

Rozumiem, że \(\displaystyle{ \varphi(16)=8}\), ale skąd się wzieła 3 w tym zapisie: \(\displaystyle{ 3^{8} \equiv 1\pmod{16}}\)?

[Ponewor]

Z twierdzenia Eulera wiemy, że \(\displaystyle{ a^{8} \equiv 1 \pmod{16}}\) o ile tylko \(\displaystyle{ a}\) jest względnie pierwsze z \(\displaystyle{ 16}\). Tak się składa, że \(\displaystyle{ 3}\) jest względnie pierwsze z \(\displaystyle{ 16}\).

[conradtbg]

Z twierdzenia Eulera wiemy, że \(\displaystyle{ a^{8} \equiv 1 \pmod{16}}\) o ile tylko \(\displaystyle{ a}\) jest względnie pierwsze z \(\displaystyle{ 16}\). Tak się składa, że \(\displaystyle{ 3}\) jest względnie pierwsze z \(\displaystyle{ 16}\).

3 jest względnie pierwsze z 16, to się zgadza. Ale czemu 3? 5 czy 7 też jest względnie pierwsze z 16.

[Ponewor]

Bo zadanie sprowadziło się do policzenia \(\displaystyle{ 3^{101}}\) i chcemy to zrobić z użyciem tego twierdzenia.

[vpprof]

Chodzi o to, żeby przedstawić prościej \(\displaystyle{ 13^{101}}\). Fakt, że \(\displaystyle{ 5^8 \equiv 1 \pmod{16}}\) w niczym ci nie pomoże.

Można zapisać tak: ponieważ \(\displaystyle{ \left( 13,16\right) =1}\), to \(\displaystyle{ 13^{101} \equiv \left( 13^{8}\right)^{12} \cdot 13^5 \equiv 13^5 \equiv \left( -3\right)^5 \pmod{16}}\) i dalej jak Vax.