Hey,
Poszukuje dowodu na to że
\(\displaystyle{ a^{b}\pmod{p} = \left( a \pmod{p} \right) ^{b}}\)
Potęgowanie modulo
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Potęgowanie modulo
Nosowska solo,
obawiam się, że to nie jest w ogólności prawdą [chyba że to jakaś niejednoznaczność w zapisie].
Niech \(\displaystyle{ a=2, b=3, p=5}\)...
Chyba że chodzi Ci o coś takiego:
lewa strona to reszta z \(\displaystyle{ a^{b}}\) modulo \(\displaystyle{ p}\), a prawa strona to reszta modulo \(\displaystyle{ p}\) z reszty a modulo \(\displaystyle{ p}\) podniesionej do potęgi \(\displaystyle{ b}\), tj. również to potęgowanie po prawej odbywa się w \(\displaystyle{ \ZZ_{p}}\) (lub ta równość jest modulo pe). W takim wypadku można to wykazać z grubsza tak:
niech \(\displaystyle{ a\equiv r\pmod{p}}\) i \(\displaystyle{ r \in\left\{ 0,...p-1\right\}}\). Wtedy możemy zapisać \(\displaystyle{ a=kp+r}\) dla pewnego (a nawet dokładnie jednego dla danego \(\displaystyle{ a}\) i danego \(\displaystyle{ p}\)) \(\displaystyle{ k \in \ZZ}\). Z dwumianu Newtona łatwo wywnioskować, że \(\displaystyle{ (kp+r)^{b}\equiv r^{b}\pmod{p}}\) i to by było na tyle. Aha, jeszcze jest przypadek \(\displaystyle{ b=0}\), gdzie tak nie można zrobić, ale wtedy teza jest oczywista.
Ale jeśli ktoś to tak oznacza, to uważam, że jest to średnio zrozumiałe i, co nie jest bez znaczenia, nieestetyczne.
obawiam się, że to nie jest w ogólności prawdą [chyba że to jakaś niejednoznaczność w zapisie].
Niech \(\displaystyle{ a=2, b=3, p=5}\)...
Chyba że chodzi Ci o coś takiego:
lewa strona to reszta z \(\displaystyle{ a^{b}}\) modulo \(\displaystyle{ p}\), a prawa strona to reszta modulo \(\displaystyle{ p}\) z reszty a modulo \(\displaystyle{ p}\) podniesionej do potęgi \(\displaystyle{ b}\), tj. również to potęgowanie po prawej odbywa się w \(\displaystyle{ \ZZ_{p}}\) (lub ta równość jest modulo pe). W takim wypadku można to wykazać z grubsza tak:
niech \(\displaystyle{ a\equiv r\pmod{p}}\) i \(\displaystyle{ r \in\left\{ 0,...p-1\right\}}\). Wtedy możemy zapisać \(\displaystyle{ a=kp+r}\) dla pewnego (a nawet dokładnie jednego dla danego \(\displaystyle{ a}\) i danego \(\displaystyle{ p}\)) \(\displaystyle{ k \in \ZZ}\). Z dwumianu Newtona łatwo wywnioskować, że \(\displaystyle{ (kp+r)^{b}\equiv r^{b}\pmod{p}}\) i to by było na tyle. Aha, jeszcze jest przypadek \(\displaystyle{ b=0}\), gdzie tak nie można zrobić, ale wtedy teza jest oczywista.
Ale jeśli ktoś to tak oznacza, to uważam, że jest to średnio zrozumiałe i, co nie jest bez znaczenia, nieestetyczne.