Czy mógłby mi ktoś wyjaśnić dokładniej jak działa modulo?
Mam dużą liczbę (zakładamy x do potęgi y) i liczbę przez którą dzielimy, mam za pomocą modulo wyznaczyć resztę z dzielenia.
Byłbym wdzięczny za wyjaśnienie.
Modulo, dzielenie dużych liczb.
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Modulo, dzielenie dużych loczb.
Rozumiem, że chodzi ci o kongruencje, tak?
Więc generalnie:
Jeśli mamy dwie liczby
\(\displaystyle{ x \equiv_n z}\)
Oznacza to, że liczba \(\displaystyle{ x}\) przy dzieleniu przez \(\displaystyle{ n}\) daje resztę \(\displaystyle{ z}\) (przy czym w zapisie kongruencji dozwolone są liczby ujemne, co ułatwia wiele spraw). Z zapisu tego wynika, że liczba
\(\displaystyle{ (x-z)|n}\)
W oczywisty sposób staramy się, aby z miało jak najmniejszą wartość bezwzględną i korzystamy z własności kongruencji
Np. \(\displaystyle{ 5 \equiv_6 -1}\)
Wówczas \(\displaystyle{ 5^7 \equiv_6 -1^7 = -1 \equiv_6 5}\)
A jakiś inny przykład:
\(\displaystyle{ 182 \equiv_{213} -31}\)
\(\displaystyle{ 182^x \equiv_{213} (-31)^x}\)
A ostatecznie zmieniasz z powrotem na liczbę dodatnią.
\(\displaystyle{ 7 \equiv_{13} -6}\)
\(\displaystyle{ 7^x \equiv_{13} (-6)^x}\)
\(\displaystyle{ 49 \equiv_{13} 36 \equiv_{13} 10}\)
Więc generalnie:
Jeśli mamy dwie liczby
\(\displaystyle{ x \equiv_n z}\)
Oznacza to, że liczba \(\displaystyle{ x}\) przy dzieleniu przez \(\displaystyle{ n}\) daje resztę \(\displaystyle{ z}\) (przy czym w zapisie kongruencji dozwolone są liczby ujemne, co ułatwia wiele spraw). Z zapisu tego wynika, że liczba
\(\displaystyle{ (x-z)|n}\)
W oczywisty sposób staramy się, aby z miało jak najmniejszą wartość bezwzględną i korzystamy z własności kongruencji
Np. \(\displaystyle{ 5 \equiv_6 -1}\)
Wówczas \(\displaystyle{ 5^7 \equiv_6 -1^7 = -1 \equiv_6 5}\)
A jakiś inny przykład:
\(\displaystyle{ 182 \equiv_{213} -31}\)
\(\displaystyle{ 182^x \equiv_{213} (-31)^x}\)
A ostatecznie zmieniasz z powrotem na liczbę dodatnią.
\(\displaystyle{ 7 \equiv_{13} -6}\)
\(\displaystyle{ 7^x \equiv_{13} (-6)^x}\)
\(\displaystyle{ 49 \equiv_{13} 36 \equiv_{13} 10}\)
-
- Użytkownik
- Posty: 3
- Rejestracja: 29 mar 2017, o 17:10
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 1 raz
Modulo, dzielenie dużych liczb.
Jak wyglądałoby to na przykładzie 10 do potęgi 20, a cała liczba ma być podzielna przez 28?
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Modulo, dzielenie dużych liczb.
\(\displaystyle{ 100 \equiv_{28} 16 \\
10000 \equiv_{28} 256 \equiv_{28} 4 \\
10^4 \equiv_{28} 4 \\
10^{20} = 10^{4^5} \equiv_{28} 4^5}\)
I jeszcze zauważasz, że \(\displaystyle{ 4^4 \equiv_{28} 4}\)
Więc \(\displaystyle{ 10^{20} \equiv_{28} 16}\)
10000 \equiv_{28} 256 \equiv_{28} 4 \\
10^4 \equiv_{28} 4 \\
10^{20} = 10^{4^5} \equiv_{28} 4^5}\)
I jeszcze zauważasz, że \(\displaystyle{ 4^4 \equiv_{28} 4}\)
Więc \(\displaystyle{ 10^{20} \equiv_{28} 16}\)
- Rafsaf
- Użytkownik
- Posty: 466
- Rejestracja: 19 lut 2017, o 11:04
- Płeć: Mężczyzna
- Lokalizacja: Podkarpacie/Wrocław
- Podziękował: 54 razy
- Pomógł: 80 razy
Modulo, dzielenie dużych liczb.
Kod: Zaznacz cały
http://www.ftj.agh.edu.pl/~lenda/number_theory/A31.pdf
O ile kojarzę to chyba nie jest to sprzeczne z regulaminem bym ten link umieścił, powinno pomóc.
A ogólnie to jest na tym forum możliwość jednoznacznego zapisu kongruencji w latex a nie kombinowania
Np.
\(\displaystyle{ x \equiv y \pmod{m}}\)
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Modulo, dzielenie dużych liczb.
Mój zapis też jest jednoznaczny i też jest jednym z "dopuszczalnych", "oficjalnych", "bez kombinowania"Rafsaf pisze:Kod: Zaznacz cały
http://www.ftj.agh.edu.pl/~lenda/number_theory/A31.pdf
O ile kojarzę to chyba nie jest to sprzeczne z regulaminem bym ten link umieścił, powinno pomóc.
A ogólnie to jest na tym forum możliwość jednoznacznego zapisu kongruencji w latex a nie kombinowania
Np.
\(\displaystyle{ x \equiv y \pmod{m}}\)