Określ postac liczb podzielnych przez *
-
- 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 *
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?
Re: Określ postac liczb podzielnych przez *
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ść:
-
- 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 *
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?
Re: Określ postac liczb podzielnych przez *
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.