Matematické Fórum

martin21 · 30. 05. 2011 13:22

Zdravím,
potřeboval bych poradit s tímto příkladem : určete zbytek při dělení čísla 2^(100) číslem 13
Nějak vůbec netuším, jak bych to měl dělat. Z přednášek si matně pamatuji, že na to byla nějaká jedna věta :-(
Díky všem, co poradí ;-)

musixx · 30. 05. 2011 13:39

Eulerova věta, resp. i jen malá Fermatova věta ti poradí, jak snížit exponent 100 na něco, co se pak dá snadno dopočítat i z hlavy.

Geronimo · 30. 05. 2011 15:01

Já bych to zase počítal takto:

Určíš si řád prvku 2 v $\mathbb{Z}^*_{13}$ .

Řád prvku a je takové nejmenší k, že platí $a^k=[1]_{13}$

K nalezení řádu by ti mohla pomoci tato věta: Řád prvku dělí řád (velikost) grupy (u konečné grupy).
A velikost grupy $\mathbb{Z}^*_{13}$ zjistíš podle Eulerovy funkce.

Když budeš znát řád 2 (nazvěme jej k), tak potom pomocí 100 mod k zjistíš exponent n a výsledek bude $[2^{100}]_{13}=[2^n]_{13}$

anes · 30. 05. 2011 15:23

Nebo na to jít naprosto jednoduše odspodu.
$2^4 = 16 \equiv 3 \pmod{13}$
$2^8 = \left( 2^4 \right) ^2 \equiv 9 \pmod{13}$
$2^{16} = \left( 2^8 \right) ^2 \equiv 81 \equiv 3 \pmod{13}$
... když budeš pokračovat, tak celekm snadno seskládáš těch 2^100

Matematické Fórum

#1 30. 05. 2011 13:22

Určení zbytku - DMA

#2 30. 05. 2011 13:39

Re: Určení zbytku - DMA

#3 30. 05. 2011 15:01

Re: Určení zbytku - DMA

#4 30. 05. 2011 15:23

Re: Určení zbytku - DMA

Zápatí