Coś innego niż małe twierdzenie fermata?

[7keN]

Witam,

Wiadomo, że aby zaszło małe twierdzenie fermata liczba pod modułem musi być liczbą pierwszą, raz liczba pod potęgą nie może być wielokrotnością tej liczby. Za pomocą tego twierdzenia można rozwiązać wiele zadań, ale co jeśli mamy do zrobienia takie zadanie:

\(\displaystyle{ 13^{234}\pmod{8}}\)

Co zrobić w takim wypadku? Jakiego twierdzenia użyć? W jaki sposób?

[kerajs]

\(\displaystyle{ 13^{234}\pmod{8}= (8+5)^{234}\pmod{8}=5^{234}\pmod{8}=25^{117}\pmod{8}=\\= (24+1)^{117}\pmod{8}=1^{117}\pmod{8}=1}\)

[7keN]

No okej tym sposobem zrobiłeś akurat ten przykład, ale następny przykład który mam do zrobienia tym sposobem już sie nie da zrobić..

\(\displaystyle{ 15 ^{552} \pmod{12}}\)

Tzn. niby się da ale te obliczenia są dziwne i długie..

\(\displaystyle{ 15 ^{552} \pmod{12} = (12+3) ^{552}\pmod{12} = 3 ^{552} \pmod{12} = 9 ^{276} \pmod{12}= 81 ^{138} \pmod{12}= 9 ^{138} \pmod{12}= 81 ^{69}\pmod{12}= 729 ^{23}\pmod{12} = 9 ^{23} \pmod{12}=}\)
i w sumie w tym momencie nie wiem co..

[Zahion]

Przecież \(\displaystyle{ 16 | 12^{2} = 144 = 16\cdot9}\) więc tym bardziej \(\displaystyle{ 12^{493}}\), stąd ta reszta oczywiście wynosi \(\displaystyle{ 0}\)
//edit
Nie edytuje się tak postów.

Ukryta treść:    

\(\displaystyle{ 12|9^{23}-9}\)

[kerajs]

Da się zrobić:
\(\displaystyle{ 9 ^{23} \pmod{12} =(9 ^{22}\cdot 9) \pmod{12}= (81 ^{11}\cdot 9 )\pmod{12}=(9 ^{11}\cdot 9)\pmod{12}=\\=81 ^{6}\pmod{12}=9 ^{6}\pmod{12}=81 ^{3}\pmod{12}=9 ^{3} \pmod{12}=\\=(81 \cdot 9)\pmod{12}=(9 \cdot 9)\pmod{12}=81\pmod{12}=9}\)

Możesz robić dowolnym sposobem. Jeśli ten Ci się nie pasuje to używaj innego. Ważne jest tylko aby był skuteczny.

[Ponewor]

Przydatne bywa twierdzenie Eulera (w pierwszym przykładzie można było wykorzystać).