Reszta z dzielenia [modulo]

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

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?
Awatar użytkownika
Janusz Tracz
Użytkownik
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]

Post autor: Janusz Tracz »

\(\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ź.
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

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 }\)?
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].
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Reszta z dzielenia [modulo]

Post autor: Premislav »

To się dzieli pisemnie z resztą, jeśli akurat tego nie zauważysz.
Awatar użytkownika
Janusz Tracz
Użytkownik
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]

Post autor: Janusz Tracz »

A jeśli chodzi o
Wasyl132 pisze: 25 lut 2020, o 16:20 I co jeżeli będe dzielił nie przez liczbę pierwszą? Np.

Jaka jest reszta z dzielenia \(\displaystyle{ 11^{50}}\) przez \(\displaystyle{ 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}\)
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

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ś"?
Jan Kraszewski
Administrator
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

Re: Reszta z dzielenia [modulo]

Post autor: Jan Kraszewski »

Wasyl132 pisze: 25 lut 2020, o 18:38Skąd \(\displaystyle{ 10^2 \cdot (\text{ coś })+5 \cdot 10+1 }\) i czym jest "coś"?
A wiesz, co to jest dwumian Newtona?

JK
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

Kojarze jakiś tam wzór na ten dwumian, ale nic poza tym, ale ten wzór chyba nie jest tutaj zastosowany?
Awatar użytkownika
Janusz Tracz
Użytkownik
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]

Post autor: Janusz Tracz »

Kojarze jakiś tam wzór na ten dwumian, ale nic poza tym, ale ten wzór chyba nie jest tutaj zastosowany?
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.
i czym jest "coś"?
\(\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.

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.
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

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ć
Awatar użytkownika
Janusz Tracz
Użytkownik
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]

Post autor: Janusz Tracz »

Wasyl132 pisze: 25 lut 2020, o 20:43 Okej, czyli rozwinięcie tego z dwumianu newtona wygląda tak:
\(\displaystyle{ 100000 + 10000 + 1000 + 100 + 10 + 1}\)
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).
Wasyl132 pisze: 25 lut 2020, o 20:43I co z tym dalej mam zrobić? Dlaczego tam jest akurat \(\displaystyle{ 10^2}\)
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}\).
Wasyl132 pisze: 25 lut 2020, o 20:43 A jeszcze wrócę do tego zapisu wcześniej - zamieniłeś \(\displaystyle{ 11^n}\) na \(\displaystyle{ (10+1)^n}\) ... Skąd wiedzieć na jakie liczy to rozbić? Domyślam się ze to zależy od liczy przez jaką dzielimy, ale wole zapytać.
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.
Wasyl132 pisze: 25 lut 2020, o 20:43 No i dalej jest \(\displaystyle{ ...+5 \cdot 10+1}\) czego tez nie do końca rozumiem.
Jak już mówiłem jedyny wzór jaki tu zastosowałem to dwumian Newtona więc zastosuj dwumian Newtona.
Sorry za takie być moze głupie pytania, ale dziś zacząłem sie tego uczyc i jeszcze nie ogarniam
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ąć.
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

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 }\)
Awatar użytkownika
Janusz Tracz
Użytkownik
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]

Post autor: Janusz Tracz »

Wasyl132 pisze: 25 lut 2020, o 22:01 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}\)
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}}\)
Wasyl132
Użytkownik
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]

Post autor: Wasyl132 »

Faktycznie, teraz juz czaje o co chodzi, dzieki wielkie za poświęcony czas :)
ODPOWIEDZ