Reszta z dzielenia wyrażenia przez 43.
-
- Użytkownik
- Posty: 22
- Rejestracja: 7 kwie 2008, o 17:49
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Podziękował: 1 raz
Reszta z dzielenia wyrażenia przez 43.
Oblicz reszte z dzielenia liczby \(\displaystyle{ 2 ^{44}-3^{85}+5 ^{211}}\) przez 43
Ostatnio zmieniony 6 gru 2008, o 15:29 przez Arek Maciejak, łącznie zmieniany 3 razy.
-
- Użytkownik
- Posty: 1420
- Rejestracja: 11 sty 2008, o 22:06
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 8 razy
- Pomógł: 411 razy
Reszta z dzielenia wyrażenia przez 43.
Małe Twierdzenie Fermata:
jeżeli p jest liczbą pierwszą, a a liczbą całkowitą, której p nie dzieli, to a podniesione do potęgi p-1 da w dzieleniu przez p resztę równą 1 :
\(\displaystyle{ a^{p-1} \equiv 1(mod \ p)}\)
\(\displaystyle{ 2^{44}=4 2^{42}=4 2^{43-1} \equiv _{MTF}4 1 (mod \ 43) \equiv 4 (mod \ 43) \\
3^{85}=3 3^{84}=3 9^{42}=3 9^{43-1}\equiv _{MTF} 3 1 (mod \ 43) \equiv 3 (mod \ 43) \\
5^{211}= 5 5^{210}=5 5^{5 42} = 5 3125^{42}=5 3125^{43-1}\equiv _{MTF}5 1 (mod \ 43) \equiv 5 (mod \ 43)}\)
więc całe wyrażenie:
\(\displaystyle{ 2^{44}-3^{85}+5^{211}\equiv_{mod \ 43}4-3+5 \equiv 6 (mod \ 43)}\)
więc reszta przy dzieleniu przez 43 to 6
jeżeli p jest liczbą pierwszą, a a liczbą całkowitą, której p nie dzieli, to a podniesione do potęgi p-1 da w dzieleniu przez p resztę równą 1 :
\(\displaystyle{ a^{p-1} \equiv 1(mod \ p)}\)
\(\displaystyle{ 2^{44}=4 2^{42}=4 2^{43-1} \equiv _{MTF}4 1 (mod \ 43) \equiv 4 (mod \ 43) \\
3^{85}=3 3^{84}=3 9^{42}=3 9^{43-1}\equiv _{MTF} 3 1 (mod \ 43) \equiv 3 (mod \ 43) \\
5^{211}= 5 5^{210}=5 5^{5 42} = 5 3125^{42}=5 3125^{43-1}\equiv _{MTF}5 1 (mod \ 43) \equiv 5 (mod \ 43)}\)
więc całe wyrażenie:
\(\displaystyle{ 2^{44}-3^{85}+5^{211}\equiv_{mod \ 43}4-3+5 \equiv 6 (mod \ 43)}\)
więc reszta przy dzieleniu przez 43 to 6