Znaleźć resztę z dzielenia
-
- Użytkownik
- Posty: 123
- Rejestracja: 25 kwie 2016, o 17:21
- Płeć: Kobieta
- Lokalizacja: Yakushima
- Podziękował: 80 razy
Znaleźć resztę z dzielenia
Znaleźć resztę z dzielenia \(\displaystyle{ 2012^{2012}}\) przez \(\displaystyle{ 11}\) i \(\displaystyle{ 55}\) przy użyciu kongruencji.
- Premislav
- 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
\(\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.
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.