Witam mam problem z tym zadaniem:
Znajdź resztę z dzielenia \(\displaystyle{ 23^{1000}}\) przez \(\displaystyle{ 61.}\)
Zapisuje i zaczynam liczyć:
\(\displaystyle{ 23^{1000}= \left( 23^{16}\right)^{60} \cdot 23^{40}}\)
\(\displaystyle{ 23^{2}=x\bmod \,61 }\)
\(\displaystyle{ 23^{2}=529\bmod\,61 }\)
\(\displaystyle{ 23^{4}=43\bmod\,61 }\)
\(\displaystyle{ 23^{4}= 43^{2} \bmod\,61 }\)
\(\displaystyle{ 23^{4}= 1849\bmod\,61 }\)
\(\displaystyle{ 23^{4}= 19\bmod\,61 }\)
\(\displaystyle{ 23^{8}= 361\bmod\,61 }\)
itd i dochodzę do
\(\displaystyle{ 23^{128}= 361\bmod\,61 }\) i nie wiem co dalej...
mod - modulo czyli reszta z dzielenia
Znajdź resztę z dzielenia...
- Mariusz M
- Użytkownik
- Posty: 6909
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Re: Znajdź resztę z dzielenia...
\(\displaystyle{ 23^{1000}\equiv\left( 23^{60}\right)^{16} \cdot 23^{40}\left( \mod 61\right)\\
23^{1000}\equiv 23^{40}\left( \mod 61\right)\\
529 \equiv 41 \left( \mod 61\right) \\
1681 \equiv 34\left( \mod 61\right) \\
23^5 \equiv 50 \left( \mod 61\right) \\
23^{10}\equiv 60 \left( \mod 61\right)\\
23^{20}\equiv 1 \left( \mod 61\right)\\
23^{40}\equiv 1 \left( \mod 61\right)\\
}\)
23^{1000}\equiv 23^{40}\left( \mod 61\right)\\
529 \equiv 41 \left( \mod 61\right) \\
1681 \equiv 34\left( \mod 61\right) \\
23^5 \equiv 50 \left( \mod 61\right) \\
23^{10}\equiv 60 \left( \mod 61\right)\\
23^{20}\equiv 1 \left( \mod 61\right)\\
23^{40}\equiv 1 \left( \mod 61\right)\\
}\)
-
- Użytkownik
- Posty: 6
- Rejestracja: 29 lis 2018, o 21:28
- Płeć: Mężczyzna
- Lokalizacja: Podlaskie
- Podziękował: 1 raz
Re: Znajdź resztę z dzielenia...
Skąd już na początku wiadomo, że
\(\displaystyle{ 23^{1000}\equiv 23^{40}\left( \mod 61\right)\\}\)
\(\displaystyle{ 23^{1000}\equiv 23^{40}\left( \mod 61\right)\\}\)