Reszta z dzielenia [modulo]

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

[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]

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 }\)?

[Premislav]

To się dzieli pisemnie z resztą, jeśli akurat tego nie zauważysz.

[Janusz Tracz]

A jeśli chodzi o

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]

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]

Skąd \(\displaystyle{ 10^2 \cdot (\text{ coś })+5 \cdot 10+1 }\) i czym jest "coś"?

A wiesz, co to jest dwumian Newtona?

JK

[Wasyl132]

Kojarze jakiś tam wzór na ten dwumian, ale nic poza tym, ale ten wzór chyba nie jest tutaj zastosowany?

[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]

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ć

[Janusz Tracz]

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).

I 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}\).

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.

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]

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 }\)

[Janusz Tracz]

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]

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