Wyznaczyć resztę dzielenia
-
- Użytkownik
- Posty: 95
- Rejestracja: 25 cze 2016, o 13:21
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wyznaczyć resztę dzielenia
Przy pomocy kongruencji wyznacz resztę dzielenia \(\displaystyle{ 3^{40} + 5^{40}}\) przez 13.
Wyznaczyć resztę dzielenia
Wystarczy wyznaczyć osobno reszty dla każdego składnika i potem dodać je modulo \(\displaystyle{ 13}\). Wyznaczanie reszt z dzielenia potęg jest bardzo łatwe.
Opisany algorytm polega na dodawaniu kongruencji, ich mnożeniu przez liczby oraz potęgowaniu.
Opisany algorytm polega na dodawaniu kongruencji, ich mnożeniu przez liczby oraz potęgowaniu.
-
- Użytkownik
- Posty: 95
- Rejestracja: 25 cze 2016, o 13:21
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wyznaczyć resztę dzielenia
A jeżeli byłoby odjemowanie to odejmuje ? A jak zrobić w drugą strone ?-- 3 gru 2016, o 22:59 --Reszta z dzielenia \(\displaystyle{ 3^{40}}\) przez 13 to 1(mod13) a \(\displaystyle{ 5^{40}}\) to 12(mod13) czyli 1+12=13 i reszta to 13?
Wyznaczyć resztę dzielenia
Odejmować też można. Ale modulo dzielnik.
Mówiłem o dodawaniu reszt modulo \(\displaystyle{ 13}\). Więc...
Nie sprawdzałem poprawności wyznaczenia reszt ze składników.
Mówiłem o dodawaniu reszt modulo \(\displaystyle{ 13}\). Więc...
Nie sprawdzałem poprawności wyznaczenia reszt ze składników.
Wyznaczyć resztę dzielenia
Dodałem czy dodałam? Twoja płeć użytkownika jest żeńska.
Mówiłem - dodaj modulo \(\displaystyle{ 13}\). Więc... Ile to \(\displaystyle{ (1+12) \mod 13}\)?
Mówiłem - dodaj modulo \(\displaystyle{ 13}\). Więc... Ile to \(\displaystyle{ (1+12) \mod 13}\)?
-
- Użytkownik
- Posty: 95
- Rejestracja: 25 cze 2016, o 13:21
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wyznaczyć resztę dzielenia
Przepraszam, bład klaiwatury...
Dodałam.
Czy mógłbyś mi to jaśniej wytłumaczyć ?
Robię to tak:
\(\displaystyle{ 3^{1}=3 \ \\
3^{2}=9 \ \
3^{3}=27 \equiv 1(mod13) \ \\
(3^{3})^{33} 3^{1} \equiv 3(mod13) \ \\
5^{1}=5 \ \\
5^{2}=25 \equiv 12(mod13) \ \\
(5^{2})^{20} \equiv 12(mod13)}\) \
czyli reszta to 3+12=15?
Dodałam.
Czy mógłbyś mi to jaśniej wytłumaczyć ?
Robię to tak:
\(\displaystyle{ 3^{1}=3 \ \\
3^{2}=9 \ \
3^{3}=27 \equiv 1(mod13) \ \\
(3^{3})^{33} 3^{1} \equiv 3(mod13) \ \\
5^{1}=5 \ \\
5^{2}=25 \equiv 12(mod13) \ \\
(5^{2})^{20} \equiv 12(mod13)}\) \
czyli reszta to 3+12=15?
Wyznaczyć resztę dzielenia
1. \(\displaystyle{ 3^{40}=3\cdot (3^3)^{13}}\). Ale idea dobra.
2. Dlaczego \(\displaystyle{ 12^{20}\mod 13=12}\)? Mamy \(\displaystyle{ 5^2\equiv 12\equiv -1}\). Dlatego \(\displaystyle{ 5^{40}\equiv (-1)^{20}=1}\).
2. Dlaczego \(\displaystyle{ 12^{20}\mod 13=12}\)? Mamy \(\displaystyle{ 5^2\equiv 12\equiv -1}\). Dlatego \(\displaystyle{ 5^{40}\equiv (-1)^{20}=1}\).
-
- Użytkownik
- Posty: 95
- Rejestracja: 25 cze 2016, o 13:21
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wyznaczyć resztę dzielenia
1. Czyli robię źle?
2. Dlaczego nie może zostać 12 tylko jest -1?
Z góry dziękuję za wszystko
2. Dlaczego nie może zostać 12 tylko jest -1?
Z góry dziękuję za wszystko
Wyznaczyć resztę dzielenia
1. Przypadkiem dobrze, bo \(\displaystyle{ 3^3\equiv 1}\), więc potęga nie ma znaczenia. Ma być \(\displaystyle{ 13}\) zamiast \(\displaystyle{ 33}\).
2. \(\displaystyle{ 12\equiv -1}\), gdyż \(\displaystyle{ 12-(-1)=13}\) jest podzielne przez \(\displaystyle{ 13}\). Ogólnie \(\displaystyle{ a\equiv b\pmod{13}\iff 13\vert(a-b)}\). A zawsze łatwiej rachować na potęgach \(\displaystyle{ -1}\), jak na potęgach \(\displaystyle{ 12}\), nieprawdaż?
2. \(\displaystyle{ 12\equiv -1}\), gdyż \(\displaystyle{ 12-(-1)=13}\) jest podzielne przez \(\displaystyle{ 13}\). Ogólnie \(\displaystyle{ a\equiv b\pmod{13}\iff 13\vert(a-b)}\). A zawsze łatwiej rachować na potęgach \(\displaystyle{ -1}\), jak na potęgach \(\displaystyle{ 12}\), nieprawdaż?