potęgowanie modulo

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
FEMO
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

potęgowanie modulo

Post autor: FEMO »

jak obliczyć

\(\displaystyle{ 3^{75} \ mod \ 103}\)
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

potęgowanie modulo

Post autor: xiikzodz »

Wszystko modulo 103:

\(\displaystyle{ 3^5=243=37}\)

\(\displaystyle{ 3^6=3\cdot 37=111=8}\)

\(\displaystyle{ 3^{18}=8^3=512=-3}\)

\(\displaystyle{ 3^{72}=(-3)^4=81=6}\)

\(\displaystyle{ 3^{75}=3^{72}\cdot 3^3=6\cdot 27=162=49}\)
Awatar użytkownika
Psiaczek
Użytkownik
Użytkownik
Posty: 1502
Rejestracja: 22 lis 2010, o 09:53
Płeć: Mężczyzna
Lokalizacja: Polska, Warmia, Olsztyn :)
Podziękował: 1 raz
Pomógł: 475 razy

potęgowanie modulo

Post autor: Psiaczek »

xiikzodz pisze:Wszystko modulo 103:



\(\displaystyle{ 3^{72}=(-3)^4=81=6}\)
a może \(\displaystyle{ 81=-22}\) ?
Xitami

potęgowanie modulo

Post autor: Xitami »

\(\displaystyle{ a^1=3\\
a^2=a^1*a^1=9\\
a^3=a^2*a^1=27\\
a^6=a^3*a^3=728\equiv8\\
a^{12}=a^6*a^6=64\\
a^{15}=a^{12}*a^3=1728\equiv80\\
a^{30}=a^{15}*a^{15}=6400\equiv14\\
a^{60}=a^{30}*a^{30}=196\equiv93\\
a^{75}=a^{60}*a^{15}=7440\equiv24\\
3^{75}(\equiv24\mod103)}\)


minimalna liczba mnożeń
Awatar użytkownika
Psiaczek
Użytkownik
Użytkownik
Posty: 1502
Rejestracja: 22 lis 2010, o 09:53
Płeć: Mężczyzna
Lokalizacja: Polska, Warmia, Olsztyn :)
Podziękował: 1 raz
Pomógł: 475 razy

potęgowanie modulo

Post autor: Psiaczek »

Xitami pisze:\(\displaystyle{ a^1=3\\

a^6=a^3*a^3=728\equiv8\\

3^{75}(\equiv24\mod103)}\)


minimalna liczba mnożeń
Wynik jest dobry, w kwestii formalnej: \(\displaystyle{ 27 \cdot 27=729}\)
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

potęgowanie modulo

Post autor: xiikzodz »

Faktycznie, miało być

\(\displaystyle{ 3^5=243=37}\)

\(\displaystyle{ 3^6=3\cdot 37=111=8}\)

\(\displaystyle{ 3^{18}=8^3=512=-3}\)

\(\displaystyle{ 3^{72}=(-3)^4=81}\)

\(\displaystyle{ 3^{75}=3^{72}\cdot 3^3=81\cdot 27=81\cdot 3\cdot 9=243\cdot 9=37\cdot 9=37\cdot 3\cdot 3=111\cdot 3=8\cdot 3=24}\)

W ten sposób mnożymy małe liczby.
ODPOWIEDZ