Reszta z dzielenia [modulo]
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Reszta z dzielenia [modulo]
Cześć, wytłumaczyłby mi ktoś krok po kroku jak się wykonuje zadania tego typu?
1) Jaka jest reszta z dzielenia \(\displaystyle{ 2019^{3020} }\) przez 53?
1) Jaka jest reszta z dzielenia \(\displaystyle{ 2019^{3020} }\) przez 53?
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Reszta z dzielenia [modulo]
\(\displaystyle{ 1)}\) Zauważmy, że \(\displaystyle{ 2019= 38 \cdot 53+5}\) zatem (Dwumian Newtona):
\(\displaystyle{ 2019^n \equiv (38 \cdot 53+5)^n\equiv 5^n \bmod 53}\)
\(\displaystyle{ 2)}\) Kładziemy \(\displaystyle{ n=3020}\), po czym zauważamy, że (Twierdzenie Eulera) \(\displaystyle{ 5^{52}\equiv1 \bmod 53}\) zatem
\(\displaystyle{ 5^{3020} \equiv \left( 5^{52}\right)^{58} \cdot 5^4\equiv 5^4 \bmod 53}\)
A to już łatwo obliczyć \(\displaystyle{ 5^4 \bmod 53=42}\) i to jest odpowiedź.
\(\displaystyle{ 2019^n \equiv (38 \cdot 53+5)^n\equiv 5^n \bmod 53}\)
\(\displaystyle{ 2)}\) Kładziemy \(\displaystyle{ n=3020}\), po czym zauważamy, że (Twierdzenie Eulera) \(\displaystyle{ 5^{52}\equiv1 \bmod 53}\) zatem
\(\displaystyle{ 5^{3020} \equiv \left( 5^{52}\right)^{58} \cdot 5^4\equiv 5^4 \bmod 53}\)
A to już łatwo obliczyć \(\displaystyle{ 5^4 \bmod 53=42}\) i to jest odpowiedź.
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Okej, tylko jak mam zauważyć, że \(\displaystyle{ 2019 = 38 \cdot 58 + 5}\) ?
Dlaczego akurat tak to rozbiłeś?
I co jeżeli będe dzielił nie przez liczbę pierwszą? Np.
Jaka jest reszta z dzielenia \(\displaystyle{ 11^{50}}\) przez \(\displaystyle{ 25 }\)?
Dlaczego akurat tak to rozbiłeś?
I co jeżeli będe dzielił nie przez liczbę pierwszą? Np.
Jaka jest reszta z dzielenia \(\displaystyle{ 11^{50}}\) przez \(\displaystyle{ 25 }\)?
Ostatnio zmieniony 25 lut 2020, o 17:46 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Powód: Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Reszta z dzielenia [modulo]
A jeśli chodzi o
\(\displaystyle{ 11^{5} \equiv (10+1)^{5} \equiv 10^2 \cdot (\text{ coś })+5 \cdot 10+1 \equiv 1 \bmod 25}\)
więc ogólnie dla dowolnego \(\displaystyle{ n\in\NN}\):
\(\displaystyle{ 11^{5n} \equiv (10+1)^{5n} \equiv 1 \bmod 25}\)
zatem szczególnie dla \(\displaystyle{ n=10}\) mamy \(\displaystyle{ 11^{50}\equiv 1 \bmod 25}\)
Twierdzenie Eulera na które się powołałem nie narzuca warunku pierwszości na "dzielnik modulo" jak to ma miejsce w twierdzeniu Fermata (dlatego używam Eulera). Co do samego przykładu to można zauważyć, że
\(\displaystyle{ 11^{5} \equiv (10+1)^{5} \equiv 10^2 \cdot (\text{ coś })+5 \cdot 10+1 \equiv 1 \bmod 25}\)
więc ogólnie dla dowolnego \(\displaystyle{ n\in\NN}\):
\(\displaystyle{ 11^{5n} \equiv (10+1)^{5n} \equiv 1 \bmod 25}\)
zatem szczególnie dla \(\displaystyle{ n=10}\) mamy \(\displaystyle{ 11^{50}\equiv 1 \bmod 25}\)
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Nie bardzo rozumiem co tu się stało:
\(\displaystyle{ 11^{5} \equiv (10+1)^{5} \equiv 10^2 \cdot (\text{ coś })+5 \cdot 10+1 \equiv 1 \bmod 25}\)
Skąd \(\displaystyle{ 10^2 \cdot (\text{ coś })+5 \cdot 10+1 }\) i czym jest "coś"?
\(\displaystyle{ 11^{5} \equiv (10+1)^{5} \equiv 10^2 \cdot (\text{ coś })+5 \cdot 10+1 \equiv 1 \bmod 25}\)
Skąd \(\displaystyle{ 10^2 \cdot (\text{ coś })+5 \cdot 10+1 }\) i czym jest "coś"?
-
- Administrator
- Posty: 34073
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5191 razy
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Kojarze jakiś tam wzór na ten dwumian, ale nic poza tym, ale ten wzór chyba nie jest tutaj zastosowany?
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Reszta z dzielenia [modulo]
Jest zastosowany, właściwie to jest jedyny wzór jaki tu zastosowałem. Na tej samej zasadzie co w pierwszym poście. Bez znajomości dwumianu Newtona dużo przejść (które są stosunkowo proste) może Ci się wydać nielogiczne/nieuzasadnione/noszące znamiona jasnowidztwa.Kojarze jakiś tam wzór na ten dwumian, ale nic poza tym, ale ten wzór chyba nie jest tutaj zastosowany?
\(\displaystyle{ \text{ coś }}\) jest jakąś liczbą całkowitą która nie ma znaczenia bo obok tego \(\displaystyle{ \text{ coś }}\) stoi \(\displaystyle{ 100}\) które jest podzielne przez \(\displaystyle{ 25}\). Problemem była ostatnia \(\displaystyle{ 10}\) której nie podnośmy do potęgi większej równej \(\displaystyle{ 2}\). Jednak akurat w rozwinięciu \(\displaystyle{ (a+b)^5}\) pojawia się \(\displaystyle{ 5}\) w przedostatnim iloczynie która w iloczynie z \(\displaystyle{ 10}\) daje już liczbę podzielną przez \(\displaystyle{ 25}\) i zostaje upragnione \(\displaystyle{ 1}\). Obawiam się jednak, że ten opis może Ci jedynie zamącić bez uprzedniego zrozumiana dwumianu Newtona.i czym jest "coś"?
PS Jak bardzo chcesz to mogę napisać czym jest to \(\displaystyle{ \text{ coś }}\) ale bardziej dydaktyczne będzie gdy sam tego poszukasz to raz a dwa to jak już mówiłem \(\displaystyle{ \text{ coś }}\) nie ma tu znaczenia.
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Okej, czyli rozwinięcie tego z dwumianu newtona wygląda tak:
\(\displaystyle{ 100000 + 10000 + 1000 + 100 + 10 + 1}\)
I co z tym dalej mam zrobić? Dlaczego tam jest akurat \(\displaystyle{ 10^2}\)
A jeszcze wrócę do tego zapisu wcześniej - zamieniłeś \(\displaystyle{ 11^5}\) na \(\displaystyle{ \left( 10+1\right)^5 }\), a gdzieś w innym twoim poście wiedziałem tez \(\displaystyle{ 19^n = \left( 17+2\right)^n }\) Skąd wiedzieć na jakie liczy to rozbić? Domyślam się ze to zależy od liczy przez jaką dzielimy, ale wole zapytać.
No i dalej jest \(\displaystyle{ ... + 5 \cdot 10 + 1}\) czego tez nie do końca rozumiem.
Sorry za takie być moze głupie pytania, ale dziś zacząłem sie tego uczyc i jeszcze nie ogarniam
PS pierwszy post zrozumiałem, tylko tutaj coś nie mogę załapać
\(\displaystyle{ 100000 + 10000 + 1000 + 100 + 10 + 1}\)
I co z tym dalej mam zrobić? Dlaczego tam jest akurat \(\displaystyle{ 10^2}\)
A jeszcze wrócę do tego zapisu wcześniej - zamieniłeś \(\displaystyle{ 11^5}\) na \(\displaystyle{ \left( 10+1\right)^5 }\), a gdzieś w innym twoim poście wiedziałem tez \(\displaystyle{ 19^n = \left( 17+2\right)^n }\) Skąd wiedzieć na jakie liczy to rozbić? Domyślam się ze to zależy od liczy przez jaką dzielimy, ale wole zapytać.
No i dalej jest \(\displaystyle{ ... + 5 \cdot 10 + 1}\) czego tez nie do końca rozumiem.
Sorry za takie być moze głupie pytania, ale dziś zacząłem sie tego uczyc i jeszcze nie ogarniam
PS pierwszy post zrozumiałem, tylko tutaj coś nie mogę załapać
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Reszta z dzielenia [modulo]
Nie. A możesz pokazać wzór z jakiego skorzystałeś? Poza tym nie ma tu żadnego znaku \(\displaystyle{ =}\) więc właściwie to nawet nie wiem co rozpisałeś (choć się domyślam, jeśli \(\displaystyle{ 11^5}\) to jest to, źle).
Tak jak mówiłem \(\displaystyle{ 100}\) dzieli się przez \(\displaystyle{ 25}\) a to podzielność przez \(\displaystyle{ 25}\) badamy więc jest naturalne by wyłuskać akurat \(\displaystyle{ 100}\).
Tak to zależy od liczby przez którą dzielimy. Choć ta zależność nie podlega ścisłym definicją to raczej wyczucie i próba dopasowania która nie zawsze jest rozwiązaniem (tu była). Bywa tak, że próbujemy jakoś to dopasować i nic to nie daje, trzeba pokombinować czasem.
Jak już mówiłem jedyny wzór jaki tu zastosowałem to dwumian Newtona więc zastosuj dwumian Newtona.
To nie są głupie pytania, niektóre z nich są całkiem dobre (na gruncie kongruencji) ale zadawanie innych (w szczególność o dwumian Newtona) świadczy, że masz zaległości z którymi kongruencje będzie Ci dużo trudniej pojąć.Sorry za takie być moze głupie pytania, ale dziś zacząłem sie tego uczyc i jeszcze nie ogarniam
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Według wzoru mi wychodzi, że \(\displaystyle{ \left( 10 + 1\right)^5 = 10^5 + 5 \cdot 10^4 + 10 \cdot 10^3 + 10 \cdot 10^2 + 5 \cdot 10^4 + 10^5}\)
Korzystałem ze wzoru:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} a^{n-k} \cdot b^k }\)
Korzystałem ze wzoru:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} a^{n-k} \cdot b^k }\)
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Reszta z dzielenia [modulo]
No prawie
\(\displaystyle{ \left( 10 + 1\right)^5 = 10^5 + 5 \cdot 10^4 + 10 \cdot 10^3 + 10 \cdot 10^2 +\red{ 5 \cdot 10^1+1^5}}\)
czyli
\(\displaystyle{ \left( 10 + 1\right)^5 = 10^5 + 5 \cdot 10^4 + 10 \cdot 10^3 + 10 \cdot 10^2 +\red{ 5 \cdot 10+1}}\)
czyli
\(\displaystyle{ \left( 10 + 1\right)^5 = 10^2(10^3 + 5 \cdot 10^2 + 10^2+ 10 ) +\red{ 5 \cdot 10+1}}\)
czyli
\(\displaystyle{ \left( 10 + 1\right)^5 = \blue{25} \cdot 4(10^3 + 5 \cdot 10^2 + 10^2+ 10 ) +\red{ 5 \cdot 10+1}}\)
czyli
\(\displaystyle{ 11^{5} \equiv \red{5 \cdot 10+1} \equiv \blue{25} \cdot 2+1 \equiv 1 \bmod \blue{25}}\)
-
- Użytkownik
- Posty: 13
- Rejestracja: 5 lis 2019, o 19:30
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 7 razy
Re: Reszta z dzielenia [modulo]
Faktycznie, teraz juz czaje o co chodzi, dzieki wielkie za poświęcony czas