Matematické Fórum

Lucky11 · 10. 06. 2009 20:19

ahojda potrebovala bych radu,jak vypocitat priklad na modularni umocneni:
c=3^18 mod 8.
Dekujuuuuu

ttopi · 10. 06. 2009 20:24

Podle mě si to stačí napsat jako
$3^2\cdot 3^2\cdot 3^2\cdot 3^2\cdot 3^2\cdot 3^2\cdot 3^2\cdot 3^2\cdot 3^2$ což je jako $9\cdot9\cdot9\cdot9\cdot9\cdot9\cdot9\cdot9$ což je modulo 8 rovno 1. Ale ruku do ohně za to nedám, jen mě to napadlo.

Alesak · 10. 06. 2009 20:58

↑ ttopi:
a jak si prisel na to ze ten druhej vyraz je rovnej 1?

ttopi · 10. 06. 2009 21:01

Já vím, že je to špatně :-)

Jinak jsem si domyslel, že když má být výsledek modulo 8, tak mohu každý činitel udělat modulo 8 a pak to bude 1*1*1*.... :-)

Asi špatně, jen pokus :-D Taky jsem napsal "podle mě" :D

Alesak · 10. 06. 2009 21:07

no, podle kalkulacky to vychazi, jenom premejslim proc...

Ginco · 10. 06. 2009 21:11 — Editoval Ginco (10. 06. 2009 21:34)

$c=3^{18}(mod 8)$

$c=(3^{2})^{9}(mod 8)$
----------------------------------------
$d=9(mod 8)$

$d=1$
----------------------------------------
$c=(d)^{9}(mod 8)$

$c=(1)^{9}(mod 8)$

$c=1$

ttopi · 10. 06. 2009 21:26

↑ Ginco:
Mohu se jen zeptat, jaktože $3^{18}=\Big(3^2\Big)^{16}$ ? To ses sekl a má tam být ^9 nebo je to v rámci té modulární aritmetiky tak?

Ginco · 10. 06. 2009 21:34

↑ ttopi:

jj, to jsem se sekl :-D

opravim to a díky

musixx · 11. 06. 2009 10:29 — Editoval musixx (11. 06. 2009 10:36)

Uvaha od ttopi je v poradku. Kazde cinitele si mohu upravovat pomoci modulu, tedy je $3^{18}\equiv\left(3^2\right)^9\equiv1^9\equiv1\ ({\rm mod}\ 8)$ .

Dale lze vyuzit treba Eulerovu vetu $a^{\varphi(m)}\equiv1\ ({\rm mod}\ m)$ , kde $\varphi(8)=4$ , tedy $3^{18}\equiv\left(3^4\right)^4\cdot3^2\ ({\rm mod}\ 8)$ nebo treba rovnost $a^m\equiv a\ ({\rm mod}\ m)$ , tedy $3^{18}\equiv\left(3^8\right)^2\cdot3^2\ ({\rm mod}\ 8)$ .

EDIT: zejmena ta Eulerova veta je pomerne silny nastroj, protoze nam rika, jakym modulem muzeme "snizovat" exponent. Jde totiz o to, najit vhodne vyjadreni exponentu modulo $\varphi(m)$ , kde m je puvodni modulo.

EDIT2: Je treba si totiz uvedomit, ze v zakladech mocnin lze libovolne cislo nahradit cislem s tim kongruentnim, ale v exponentech ne. Proc? Laicky receno, na prvni pohled jsou to cisla jako cisla, ale na druhy pohled, ta cisla v zakladech mocnin jsou reprezentatni zbytkovych trid, zatimco ta cisla v exponentech jsou pouze symboly, ktere pouzivame pro zkraceny zapis nekolika nasobeni. Proto ten odlisny pristup. Kdyz si tohle clovek uvedomi, jsou veci hned jasnejsi.