jak obliczyć
\(\displaystyle{ 3^{75} \ mod \ 103}\)
potęgowanie modulo
-
- 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
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}\)
\(\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}\)
potęgowanie modulo
\(\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ń
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ń
- Psiaczek
- 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
Wynik jest dobry, w kwestii formalnej: \(\displaystyle{ 27 \cdot 27=729}\)Xitami pisze:\(\displaystyle{ a^1=3\\
a^6=a^3*a^3=728\equiv8\\
3^{75}(\equiv24\mod103)}\)
minimalna liczba mnożeń
-
- 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
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.
\(\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.