Wyznaczyć resztę dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

Przy pomocy kongruencji wyznacz resztę dzielenia \(\displaystyle{ 3^{40} + 5^{40}}\) przez 13.
szw1710

Wyznaczyć resztę dzielenia

Post autor: szw1710 »

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.
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

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?
szw1710

Wyznaczyć resztę dzielenia

Post autor: szw1710 »

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.
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

Dodałem reszty i wyszło 13...
szw1710

Wyznaczyć resztę dzielenia

Post autor: szw1710 »

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}\)?
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

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?
szw1710

Wyznaczyć resztę dzielenia

Post autor: szw1710 »

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}\).
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

1. Czyli robię źle?
2. Dlaczego nie może zostać 12 tylko jest -1?
Z góry dziękuję za wszystko
szw1710

Wyznaczyć resztę dzielenia

Post autor: szw1710 »

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ż?
bnyh6
Użytkownik
Użytkownik
Posty: 95
Rejestracja: 25 cze 2016, o 13:21
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 2 razy

Wyznaczyć resztę dzielenia

Post autor: bnyh6 »

Dziękuje bardzo. Zaczynam rozumieć kongruencje
ODPOWIEDZ