Obliczanie modulo

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
PabloG
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 30 paź 2016, o 17:42
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 1 raz

Obliczanie modulo

Post autor: PabloG »

Proszę o podpowiedź, jak zacząć poniższy przykład:

\(\displaystyle{ 55^{1201} \left( mod {143}\right)}\)
Hayran
Użytkownik
Użytkownik
Posty: 144
Rejestracja: 26 paź 2016, o 16:17
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 19 razy
Pomógł: 11 razy

Re: Obliczanie modulo

Post autor: Hayran »

Wsk.:
1. \(\displaystyle{ 143=11\cdot 13}\)
2. Małe twierdzenie Fremata
PabloG
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 30 paź 2016, o 17:42
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 1 raz

Re: Obliczanie modulo

Post autor: PabloG »

\(\displaystyle{ 55^{1201} \pmod{143}}\)
\(\displaystyle{ \varphi (143)=(11-1)(13-1)=120}\)
\(\displaystyle{ 55^{120} \equiv 1 \pmod{143}}\)
\(\displaystyle{ 55^{1201} \pmod{143} = 55 \cdot (55^{120})^{10} \pmod {143} = 55 \cdot 1^{10} \pmod{143} = 55}\)

Czy to rozwiązanie jest poprawne?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Obliczanie modulo

Post autor: Premislav »

Tak.
ODPOWIEDZ