Określ postac liczb podzielnych przez *

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
studciak123
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 19 lis 2017, o 17:30
Płeć: Mężczyzna
Lokalizacja: A kto to wie
Podziękował: 11 razy

Określ postac liczb podzielnych przez *

Post autor: studciak123 »

Określ postac liczb podzielnych przez 13, które leżą najbliżej liczby utworzonej z jedynki i miliona zer. A może ta liczba jest podzielna przez 13?
szw1710

Re: Określ postac liczb podzielnych przez *

Post autor: szw1710 »

Krótko mówiąc, musimy wyznaczyć resztę z dzielenia tej liczby przez \(\displaystyle{ 13}\). Wskazówka: \(\displaystyle{ 10^6\mod 13=1.}\)
Ukryta treść:    
studciak123
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 19 lis 2017, o 17:30
Płeć: Mężczyzna
Lokalizacja: A kto to wie
Podziękował: 11 razy

Określ postac liczb podzielnych przez *

Post autor: studciak123 »

Dla \(\displaystyle{ 10^{6}}\) jestem jeszcze w stanie znaleźć resztę modulo \(\displaystyle{ 13}\). Sposób z którego korzystam polega na policzeniu najpierw reszty modulo \(\displaystyle{ 13}\) liczby \(\displaystyle{ 10}\), potem będę w stanie policzyć \(\displaystyle{ 10^{10}}\) jako iloczyn 5 tych poprzednich wyników itd. Sposób ten jest jednak chyba niezbyt optymalny przy próbie policzenia reszty modulo \(\displaystyle{ 13}\) liczby utworzonej z jedynki i miliona zer. Dlatego mam, pytanie jak powinno to się robic optymalnie?
szw1710

Re: Określ postac liczb podzielnych przez *

Post autor: szw1710 »

Optymalnie jest tak, że reszty zachowują się w mnożeniu: \(\displaystyle{ (ab)\mod n = \bigl((a\mod n)\cdot(b\mod n)\bigr)\mod n}\). Aby wyznaczyć resztę z iloczynu, wystarczy pomnożyć reszty czynników i ewentualnie wziąć kolejną resztę. Komfortowo jest, gdy reszta jakiegoś czynnika to \(\displaystyle{ 1}\). Wtedy bezpośrednio przenosi się to na dowolnie wysokie potęgi.
ODPOWIEDZ