$3^{123} \mod 100$

Naprawdę masz rację. Jest jednak jedna drobna poprawa. Korzystając z funkcji Carmichaela , można argumentować, że mniejsza potęga$3$, a mianowicie $3^{\lambda(100)}=3^{20}\equiv 1\bmod 100$. Funkcja Carmichaela funkcji dzieli połowę funkcji totientów Eulera, gdy argument jest parzysty, a suma Eulera jest wielokrotnością$4$, co jest prawdą dla $\lambda(100)$; a zatem$3^{20}$ można wymienić $3^{40}$ w argumencie.

Na bardziej podstawowym poziomie możesz renderować $3^4=80+1$ i w ten sposób podnieść obie strony do piątej potęgi $3^{20}\equiv1\bmod 100$ jako twierdzenie dwumianowe dla $(80+1)^5$ daje wielokrotności $100$ plus $1$.

Prawidłowo, alternatywne rozwiązanie:

$$ \begin{align} 3^{123}&=\left(3^{2}\right)^{61}\cdot 3\\ &=\left(10-1\right)^{61}\cdot 3\\ &\equiv\left(\binom{61}{1}10^{1}\left(-1\right)^{60}-1\right)\cdot 3 &\mod{100}\\ &\equiv 27 &\mod100 \end{align} $$

Poprawny! Uważam, że twoja logika działa poprawnie. O ile widzę, jest to poprawne zastosowanie uogólnienia Eulera twierdzenia Fermata.$\phi(100) = 40$ a zatem $3^{40} \cong 1 \mod 100$

Jeśli potrzebujesz dalszego przekonywania, po prostu wprowadź $3^{123}$ w https://www.calculatorsoup.com/calculators/algebra/large-exponent-calculator.php.

Ponownie, niezbyt potrzebne, ale jeśli potrzebujesz konkretnego dowodu, to jest.

OP rozpoczął się od poszukiwania wzoru, ale stwierdził, że

... pomimo wielu bolesnych inspekcji nie dostarczył oczywistego użytecznego wzoru.

Możesz użyć teorii światła, aby faktycznie przewidzieć formę i strukturę wzoru.

Zauważ, że jeśli $a \in \{0,2,4,6,8\}$ i $b \in \{1,3,7,9\}$ i

$\quad 3 \times (10 a + b) \equiv 10 \,a' + b' \pmod{100} \text{ with } a',b' \in \{0,1,2,3,4,5,6,7,8,9\}$

w rzeczywistości $a' \in \{0,2,4,6,8\}$ i $b' \in \{1,3,7,9\}$.

To jest nasz główny (teoretyczny) wzór i

$\quad 3^1 \equiv 03 \pmod{100}$
$\quad 3^2 \equiv 09 \pmod{100}$
$\quad 3^3 \equiv 27 \pmod{100}$
$\quad 3^4 \equiv 81 \pmod{100}$
$\quad\text{-------------------------}$
$\quad 3^5 \equiv 43 \pmod{100}$

Łatwo jest sprawdzić, czy cyfra jednostek będzie się przesuwać

$\quad 3 \mapsto 9 \mapsto 7 \mapsto 1$

wewnątrz każdego z tych czterech cykli.

Biorąc pod uwagę, że $3$jest jednostką , możemy argumentować, że jedna z nich$4$-cykle będą się kończyć

$$\quad 01 \quad \text{the multiplicative identify}$$

i że żadne powtórzenie nie jest możliwe, dopóki nie zostanie osiągnięta tożsamość.

Ponieważ cyfra dziesiątek może poruszać się tylko po zbiorze$\{0,2,4,6,8\}$, jest ich najwyżej pięć $4$- motocykle, które należy obliczyć.

Obliczanie $2^{nd}$ $4$-cykl:

$\quad 3^5 \equiv 43 \pmod{100}$
$\quad 3^6 \equiv 29 \pmod{100}$
$\quad 3^7 \equiv 87 \pmod{100}$
$\quad 3^8 \equiv 61 \pmod{100}$
$\quad\text{-------------------------}$

Obliczanie $3^{rd}$ $4$-cykl:

$\quad 3^9 \equiv 83 \pmod{100}$
$\quad 3^{10} \equiv 49 \pmod{100}$
$\quad 3^{11} \equiv 47 \pmod{100}$
$\quad 3^{12} \equiv 41 \pmod{100}$
$\quad\text{-------------------------}$

Obliczanie $4^{th}$ $4$-cykl:

$\quad 3^{13} \equiv 23 \pmod{100}$
$\quad 3^{14} \equiv 69 \pmod{100}$
$\quad 3^{15} \equiv 07 \pmod{100}$
$\quad 3^{16} \equiv 21 \pmod{100}$
$\quad\text{-------------------------}$

W tym momencie tak naprawdę nie musimy obliczać $5^{th}$ $4$- cykl skoro wiemy, że musi to być ostatni.

Możemy teraz wykorzystać fakt, że

$\tag 1 3^{20} \equiv 1 \pmod{100}$

i wypracuj pozostałe szczegóły pytania PO.