Arytmetyka modularna.

[tangerine11]

Zadanie:

Czy \(\displaystyle{ 5^{70} = 2(mod71)}\)?

Zadanie rozwiązałam metodą zamiany wykładnika na potęgi dwójki, \(\displaystyle{ 5^{2}=25(mod71)}\), \(\displaystyle{ 5^{4}=57(mod71)}\), \(\displaystyle{ 5^{64}=57(mod71}\)), ostatecznie odpowiedź brzmi nie, bo \(\displaystyle{ 5^{70} = 1(mod71)}\).

Da się to zrobić szybciej?

[kerajs]

Można od razu z małego twierdzenia Fermata.
Jeśli \(\displaystyle{ p}\) jest pierwsza to \(\displaystyle{ a^{p-1}\equiv 1(mod \ p)}\)

[Premislav]

Jeszcze oczywiście \(\displaystyle{ a}\) nie może być podzielna przez \(\displaystyle{ p}\), ale tu rzecz jasna to działa.

[tangerine11]

Rzeczywiście, zadanie jest ewidentnie pod to twierdzenie. Dziękuję.