Równanie modulo

[teodore]

Witam,

Mam problem, czy też raczej pytanie, dot. następującej równości:

\(\displaystyle{ x \equiv 40^{11} \ (mod \ 43)}\)

Jak postępować, by obliczyć \(\displaystyle{ x}\), tzn. by ostatecznie otrzymać:

\(\displaystyle{ x \equiv 13 \ (mod \ 43)}\) ?

Ja liczyłem to w ten sposób, że rozpisywałem sukcesywnie \(\displaystyle{ 40^{11}}\) na iloczyn kilku czynników i tam, gdzie tylko mogłem, zwijałem te czynniki według arytmetyki modularnej, aż ostatecznie otrzymałem powyższą, końcową postać. Tyle tylko, że wszystko odbywało się z użyciem kalkulatora, a nie jestem pewien, czy jest to aby na pewno konieczne.

Pytanie moje brzmi, czy jest jakiś bardziej wyrafinowany sposób, by tego typu wyrażenie obliczyć? Na początku spodziewałem się, że pomocne okaże się tu twierdzenie Eulera (). Niestety, jako że \(\displaystyle{ 43}\) jest liczbą pierwszą mamy: \(\displaystyle{ \phi(43)=42}\), a nie jestem w stanie przekształcić wyrażenia \(\displaystyle{ 40^{11}}\) tak, by pojawił się tam wykładnik \(\displaystyle{ 42}\).

Z góry dziękuję za pomoc.

[Qń]

Można na przykład tak (wszystkie przystawania modulo \(\displaystyle{ 43}\)):
\(\displaystyle{ 40\equiv -3}\)
więc:
\(\displaystyle{ 40^4\equiv 81\equiv -5}\)
a zatem:
\(\displaystyle{ 40^{12}\equiv -125 \equiv 4}\)
Ponieważ odwrotnością \(\displaystyle{ 40}\) modulo \(\displaystyle{ 43}\) jest \(\displaystyle{ 14}\) (co łatwo w dwóch krokach wynika z rozszerzonego algorytmu Euklidesa), tzn. \(\displaystyle{ 14\cdot 40 \equiv 1}\), więc po pomnożeniu powyższej kongruencji stronami przez \(\displaystyle{ 14}\) dostaniemy:
\(\displaystyle{ 40^{11}\equiv 56 \equiv 13}\)

Q.

[teodore]

Dzięki serdeczne! Wszystko mi się wyjaśniło.