Znaleźć resztę z dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Ruahyin
Użytkownik
Użytkownik
Posty: 123
Rejestracja: 25 kwie 2016, o 17:21
Płeć: Kobieta
Lokalizacja: Yakushima
Podziękował: 80 razy

Znaleźć resztę z dzielenia

Post autor: Ruahyin »

Znaleźć resztę z dzielenia \(\displaystyle{ 2012^{2012}}\) przez \(\displaystyle{ 11}\) i \(\displaystyle{ 55}\) przy użyciu kongruencji.
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

Znaleźć resztę z dzielenia

Post autor: Premislav »

\(\displaystyle{ 2012\equiv -1\pmod{11}}\), więc \(\displaystyle{ 2012^{2012}\equiv (-1)^{2012}\pmod{11}}\)

A w tym drugim przypadku trzeba jeszcze rozważyć resztę z dzielenia przez \(\displaystyle{ 5:}\)
\(\displaystyle{ 2012\equiv 2\pmod{5}}\), zatem \(\displaystyle{ 2012^{2012}\equiv 2^{2012}\pmod{5}}\).
Teraz zauważmy, że \(\displaystyle{ 2^2\equiv -1\pmod{5}}\), toteż \(\displaystyle{ (2^2)^{1006}\equiv 1\pmod{5}}\).
Czyli mamy
1) \(\displaystyle{ 2012^{2012}\equiv 1\pmod{11}}\)
2) \(\displaystyle{ 2012^{2012}\equiv 1 \pmod{5}}\),
a \(\displaystyle{ 5\cdot 11=55}\) i \(\displaystyle{ \NWD(5,11)=1}\).
Kombinuj dalej.
ODPOWIEDZ