Matematické Fórum

PanTau · 15. 06. 2013 14:03

Ahoj, mám tady příklad na ,,Malá Fermatova věta,,, nechápu jak to mám použít v praxi na příkladu:

Určete zbytek při dělení čísla $3^{100}$ číslem $17$

Zkoumal jsem tento TENTO, ale nechápu stále nic.

Nevím kde a proč bere anes čísla

$2^{16} = \left( 2^8 \right) ^2 \equiv 81 \equiv 3 \pmod{13}$
$2^8 = \left( 2^4 \right) ^2 \equiv 9 \pmod{13}$
$2^4 = 16 \equiv 3 \pmod{13}$

Díky za rady

JohnPeca18 · 15. 06. 2013 14:36

no podle male fermatovy vety vis ze
$3^{16} \equiv 1 \text{ mod } 17$
Takze $3^{100}=(3^{16})^63^{4} \equiv 1^{6}3^4=13 \text{ mod } 17$

PanTau · 15. 06. 2013 15:43

↑ JohnPeca18:

$3^{16} \equiv 1 \text{ mod } 17$ - tohle chápu.

Nicméně proč $(3^{16})^{6}$ <- proč je zde 6?

JohnPeca18 · 15. 06. 2013 15:50

protoze $100=6*16+4=96+4$

PanTau · 15. 06. 2013 15:56

Děkuji, to již chápu, ještě bych potřeboval trošku objasnit :

$(3^{16})^{6}*3^{4} = 1^{6}*3^{4}$

proč : $(3^{16})^{6} = 1^{6}$ ??

JohnPeca18 · 15. 06. 2013 16:03

↑ PanTau:
to vypliva z vlastnosti
$3^{16} \equiv 1 \text{ mod } 17$
Takze $(3^{16})^{6} \equiv 1^{6} \text{ mod } 17$

PanTau · 15. 06. 2013 16:10

↑ JohnPeca18:
Aha, tak mi prosím překontroluj ještě toto:

$2^{100} mod 13$
$2^{12}=1mod13$

$2^{100}=(2^{12})^{8}*2^{4}=1^{8}*2^{4}=16mod13 = 3$

Výsledek 3 (i podle wolframu) je to tak správně? Díky!

JohnPeca18 · 15. 06. 2013 16:12

Jo presne tak :)

PanTau · 15. 06. 2013 16:13

↑ JohnPeca18:

Díky!:-)

Matematické Fórum

#1 15. 06. 2013 14:03

Malá Fermatova věta - použití v praxi

#2 15. 06. 2013 14:36

Re: Malá Fermatova věta - použití v praxi

#3 15. 06. 2013 15:43

Re: Malá Fermatova věta - použití v praxi

#4 15. 06. 2013 15:50

Re: Malá Fermatova věta - použití v praxi

#5 15. 06. 2013 15:56

Re: Malá Fermatova věta - použití v praxi

#6 15. 06. 2013 16:03

Re: Malá Fermatova věta - použití v praxi

#7 15. 06. 2013 16:10

Re: Malá Fermatova věta - použití v praxi

#8 15. 06. 2013 16:12

Re: Malá Fermatova věta - použití v praxi

#9 15. 06. 2013 16:13

Re: Malá Fermatova věta - použití v praxi

Zápatí