Przykład zastosowania twierdzenia Eulera

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$: