Modulo, dzielenie dużych liczb.

[Kryslew]

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.

[PoweredDragon]

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

[Kryslew]

Jak wyglądałoby to na przykładzie 10 do potęgi 20, a cała liczba ma być podzielna przez 28?

[PoweredDragon]

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

[Rafsaf]

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

[Kryslew]

Dziękuję bardzo! Problem rozwiązany, życzę miłego dnia

[PoweredDragon]

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

Mój zapis też jest jednoznaczny i też jest jednym z "dopuszczalnych", "oficjalnych", "bez kombinowania"