Matematické Fórum

allstar · 10. 06. 2008 17:52

Prosim nevite nekdo jak se na papire bez kalkulacky da spocitat tento priklad?

Určete zbytek při dělení čísla 4^80 číslem 13.

Dik moc.

ttopi · 10. 06. 2008 18:01 — Editoval ttopi (10. 06. 2008 18:06)

Když umocňujeme 4 na sudý mocnitel, končí číslo na $6$ , například $4^{16}=4294967296$ .
Když umocňujeme na lichý mocnitel, končí číslo na $4$ , například $4^9=262144$ .
Vidíme, že $4^{80}$ bude jistě končit na číslo $6.$
Teď jak do toho zapracovat tu 13 :-)

Saturday · 10. 06. 2008 19:25

Ja bych to udelal takto:

$4^{80} = 4^{2*40} = 16^{40} = 16 \cdot 16^{39} = 16 \cdot (16^3)^{13}$

Ted pouziju Malou Fermatovu vetu a poslední vlastnost z: http://en.wikipedia.org/wiki/Modular_ar … e_relation (tesne pred nadpisem: The ring of congruence classes )

$16 \cdot (16^3)^{13} \equiv 16 \cdot 16^3 \text{(mod 13)}$

Nyni pouziju pravidlo: (a mod n · b mod n) mod n = (a·b) mod n (http://cs.wikipedia.org/wiki/Modul%C3%A … aritmetika)

$(16 \text{(mod 13)} \cdot 16^3 \text{(mod 13)}) \text{(mod 13)} = (3 \cdot 1) \text{(mod 13)} = 3$

Pozorovani k predchozimu radku: $16^3 \text{(mod 13)} = 1$ , protoze $16^3 = 2^{12}$ a tedy podle Male Fermatovy vety: $2^{12} \equiv 1 \text{(mod 13)}$

Treba to pujde nejak jednoduseji, nicmene i kdyz se to muze zdat tezke, tak je muj postup hodne primitivni.. :)

Kondr · 10. 06. 2008 21:35

Teorii čísel mám rád, takže přihodím ještě pro inspiraci jednu cestu.
Protože
$4^3\equiv64\equiv-1 \pmod{13}$
máme
$4^{80}\equiv4^{3*26+2}\equiv(-1)^{26}4^2\equiv 16\equiv 3 \pmod{13}$

@Saturday: pokud chceš ušetřit čas s TeXováním, používej \pmod

Saturday · 10. 06. 2008 21:46

↑ Kondr: Priste zkusim, diky :)

Matematické Fórum

#1 10. 06. 2008 17:52

Kongruence modulo

#2 10. 06. 2008 18:01 — Editoval ttopi (10. 06. 2008 18:06)

Re: Kongruence modulo

#3 10. 06. 2008 19:25

Re: Kongruence modulo

#4 10. 06. 2008 21:35

Re: Kongruence modulo

#5 10. 06. 2008 21:46

Re: Kongruence modulo

Zápatí