Ładowanie
Angielski
Rosyjski
Strona domowa Mikołaja Hajduka

Przykład zastosowania twierdzenia Eulera

Z
ałóżmy, że przedstawiono nam do rozwiązania następujące zadanie: obliczyć wartość wyrażenia \[3^{3333333} \mod 100\] tj. mamy wyznaczyć resztę z dzielenia $3^{3333333}$ przez $100$. Innymi słowy chodzi nam o określenie dwóch ostatnich cyfr reprezentacji liczby $3^{3333333}$ w systemie dziesiątkowym. Na pierwszy rzut oka problem nie wygląda zbyt zachęcająco od strony rachunkowej; wydawać by się mogło, iż czeka nas sporo żmudnej i niezbyt pouczającej pracy. Jak się jednak okaże, zadania tego typu można rozwiązywać korzystając ze swego rodzaju "skrótów", które szybko doprowadzają nas do wymaganego wyniku.

Jeśli liczba potęgowana $a$, tj. w naszym przypadku $a = 3$, jest względnie pierwsza z modułem $m$ (tutaj $m = 100$), to wówczas istnieje taka liczba naturalna $k > 0$, dla której zachodzi kongruencja \[a^{k} \equiv 1 \; (\mkern-18mu \mod m) \; \; (*)\] W rzeczy samej, twierdzenie Eulera, mówi nam, że taka kongruencja zachodzi dla $k = \phi(m)$, gdzie $\phi(n)$ jest nazywana funkcją Eulera (inaczej tocjentem) i jej wartość określona jest dla dowolnego naturalnego $n$ jako ilość liczb względnie pierwszych z $n$ nie większych od $n$. Co ciekawe, $\phi(m)$ nie musi być jedyną liczbą naturalną, dla której spełniona jest wyżej wspomniana kongruencja (*). W rzeczy samej, omawiane tutaj przez nas zadanie jest przykładem takiego przypadku, w którym kongruencja (*) spełniona jest dla także liczby dużo mniejszej od $\phi(m)$.

Dlaczego fakt istnienia takiej liczby naturalnej $k > 0$, że dla względnie pierwszych $a$ i $m$ zachodzi \[a^{k} \equiv 1 \; (\mkern-18mu \mod m)\] jest tak ważny? Ano dlatego, że wówczas do obliczenia \[a^{n} \mkern-18mu \mod m\] wystarczy wziąć \[a^{n \mkern-8mu \mod k} \mkern-18mu \mod m\] albowiem jeśli $n = sk + r$ dla naturalnego $s > 0$ i $0 \leq r < k$, to mamy \[(a^{k})^{s} \equiv 1 \; (\mkern-18mu \mod m)\] tj. \[a^{sk} \equiv 1 \; (\mkern-18mu \mod m)\] mnożąc następnie obustronnie przez $a^{r}$ przekształcamy tę kongruencję do postaci \[a^{sk}*a^{r} \equiv a^{r} \; (\mkern-18mu \mod m)\] czyli \[a^{sk+r} \equiv a^{r} \; (\mkern-18mu \mod m)\] korzystając z tego, że $n = sk + r$ możemy to przystawanie zapisać w następujący sposób: \[a^{n} \equiv a^{n \mkern-8mu \mod k} \; (\mkern-18mu \mod m)\] Otrzymana wyżej zależność pozwala redukować wykładniki do wielkości umożliwiających wykonanie potęgowania nawet za pomocą prostego kalkulatora.

Opierając się na definicji funkcji Eulera obliczymy teraz wartość $\phi(100)$: \[\phi(100) = 100\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 100\frac{1}{2}\frac{4}{5} = 40\] Zatem \[3^{3333333} \equiv 3^{3333333 \mod 40}\; (\mkern-18mu \mod 100)\] tj. \[3^{3333333} \equiv 3^{13} = 1594323 \; (\mkern-18mu \mod 100)\] i ostatecznie \[3^{3333333} \equiv 23 \; (\mkern-18mu \mod 100)\]

Zauważmy, że gdybyśmy chcieli znaleźć empirycznie najmniejszy taki wykładnik $k > 0$, dla którego zachodzi \[3^{k} \equiv 1 \; (\mkern-18mu \mod 100) \; \; (**)\] to wystarczyłoby sprawdzić tylko $20$ początkowych liczb naturalnych. Istotnie, \[3^{20} = 3486784401 \equiv 1 \; (\mkern-18mu \mod 100)\] Jest to właśnie przykład sytuacji, w której funkcja Eulera nie daje najmniejszej liczby liczby naturalnej spełniającej równanie (**).

Ci spośród Czytelników, których niniejszy temat zainteresował i chcieliby się naocznie przekonać o prawdziwości powyższego stwierdzenia, zapewne na koniec zechcą rzucić okiem na taką oto tablicę zawierająca $20$ najmniejszych potęg liczby $3$ wraz z odpowiadającymi im resztami modulo $100$:

$k$$3^{k}$$3^{k} \mod 100$
$1$$3$$3$
$2$$9$$9$
$3$$27$$27$
$4$$81$$81$
$5$$243$$43$
$6$$729$$29$
$7$$2187$$87$
$8$$6561$$61$
$9$$19683$$83$
$10$$59049$$49$
$11$$177147$$47$
$12$$531441$$41$
$13$$1594323$$23$
$14$$4782969$$69$
$15$$14348907$$7$
$16$$43046721$$21$
$17$$129140163$$63$
$18$$387420489$$89$
$19$$1162261467$$67$
$20$$3486784401$$1$
© 2007-2014, Mikołaj Hajduk