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?
Arytmetyka modularna.
-
- Użytkownik
- Posty: 207
- Rejestracja: 23 paź 2015, o 12:31
- Płeć: Kobieta
- Lokalizacja: Mielec
- Podziękował: 14 razy
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Arytmetyka modularna.
Jeszcze oczywiście \(\displaystyle{ a}\) nie może być podzielna przez \(\displaystyle{ p}\), ale tu rzecz jasna to działa.
-
- Użytkownik
- Posty: 207
- Rejestracja: 23 paź 2015, o 12:31
- Płeć: Kobieta
- Lokalizacja: Mielec
- Podziękował: 14 razy