Arytmetyka modularna , funkcja Eulera.

[Sadczi]

Witam.

Pilnie potrzebuję pomocy z dwoma przykładami.
Natknąłem się wcześniej na podobne zadania , lecz nie jestem pewien czy do końca rozumiem wszystko.
Będą sprawdzany z o wiele trudniejszych przykładów niż były w tamtym temacie więc potrzebuję by ktoś pokazał mi jak to się robi. Jak widać po tytule funkcja eulera powinna być wykorzystana , oraz własności jego praw. Oto przykłady z którymi borykam się , mile widziane tłumaczenie kroków.

\(\displaystyle{ 3 ^{7843} \pmod{13}}\)
\(\displaystyle{ 3 ^{7843} \pmod{12}}\)

Pozdrawiam

[sebnorth]

\(\displaystyle{ (3,13) = 1}\) czyli z twierdzenia Eulera \(\displaystyle{ 3^{\phi(13)} \equiv 1 \pmod{13}}\)

\(\displaystyle{ \phi(13) = 13 - 1 = 12}\).

Dalej: \(\displaystyle{ 12 \cdot 653 = 7836, \; (3^{\phi(13)})^{653} \equiv 1 \pmod{13}, \; 3^{7836} \cdot 3^7 \equiv 3^7 \pmod{13}}\)

łatwo sprawdzić, że \(\displaystyle{ 3^{7} \equiv 3 \pmod{13}}\) (np. przy użyciu kalkulatora prostego)

\(\displaystyle{ (3,4) = 1}\) czyli z twierdzenia Eulera \(\displaystyle{ 3^{\phi(4)} \equiv 1 \pmod{4}}\)

\(\displaystyle{ \phi(4) = 2}\)

czyli \(\displaystyle{ 3^{7842} \equiv 1 \pmod{4}}\), czyli \(\displaystyle{ 3^{7843} \equiv 3 \pmod{4}}\).

Ponadto \(\displaystyle{ 3^{7843} \equiv 3 \pmod{3}}\) bo 3 dzieli \(\displaystyle{ 3^{7843} - 3}\).

Skoro \(\displaystyle{ (3,4) = 1}\) to \(\displaystyle{ 3\cdot 4}\) dzieli \(\displaystyle{ 3^{7843} - 3}\) a to znaczy że \(\displaystyle{ 3^{7843} \equiv 3 \pmod{12}}\).

[Sadczi]

hmm. Nie wiem skąd się biorą niektóre rzeczy. Czy mógłbyś napisać mi jakiś prosty algorytm krok po kroku jak to robisz najlepiej z wzorami z których dany krok wynika? Przepraszam że jestem tak ciężko kumający ale proszą o litość , ja naprawdę muszę to umieć:)

[sebnorth]

to może zacznijmy od tego co wiesz a co nie, czy wiesz dlaczego

\(\displaystyle{ \phi(4) = 2}\)

?

[Sadczi]

Tak wiem to. Tylko dalej juz sie gubię:P 12 * 653 to magia dla mnie. A dalej odrobinkę wyjaśnienia co jest co powinienem sobie poradzić

[sebnorth]

podnosimy obie strony kongruencji do potęgi 653 żeby było blisko wykładnika 7843

[Sadczi]

Właściwie odpowiadając na pytanie że rozumiem \(\displaystyle{ \phi(4)= 2}\) nie byłem do końca szczery. Oczywiście rozumiem wynik działania , ale dlaczego w tym przykładzie jest 4? Domyślam się by NWD wyszedł 1. Ale kolejne wnioski (dwie ostatnie linijki) tworzą u mnie wątpliwości. Skąd wiemy że \(\displaystyle{ 3^{7843} - 3}\) jest podzielne przez 3? i że 3 * 4 dzieli tą liczbę?

[sebnorth]

\(\displaystyle{ \phi(4)= 2}\) potrzebne jest do twierdzenia Eulera,

3 dzieli \(\displaystyle{ 3^{7843} - 3}\) ponieważ 3 dzieli odjemną, odjemnik a więc i różnicę

jeśli \(\displaystyle{ m,n}\) są względnie pierwsze i m oraz n dzielą jakąś liczbę A powiedzmy, to \(\displaystyle{ m\cdot n}\) również dzieli A

[Sadczi]

Dziękuję za pomoc , teraz wszystko juz jest jasne