Matematické Fórum

hipot · 03. 03. 2014 17:36 — Editoval hipot (03. 03. 2014 17:36)

Dobrý den,

Potřeboval bych poradit.
Snažím se přijít na způsob řešení příkladů typu "Zjistěte jaký je zbytek po dělení čísla 2^60 (mod 13)?".

Na cvičení se tento příklad řešil pomocí kongruentních čísel.
Vypozoroval jsem několik pravidel, kterými se zřejmě výpočet řídí, ale nedaří se mi postup zopakovat na jiných číslech.
1. Myslím, že cílem je získat číslo kongruentní s 1 nebo -1, takové číslo se jednoduše umocní.
2. Myslím, že je potřeba dělat takové úpravy, aby bylo možné získat umocněním zpět původní číslo.
3. Na kongruenci se zřejmě můžeme dívat jako na rovnici, obě strany můžeme mocnit a násobit bez ztráty stejného zbytku po dělení stejným modulem.

Nicméně něco mi uniká, protože toto samotné nestačí na vyřešení libovolného příkladu.
Mohl by mi někdo poradit, jak na to?

Níže vzorový příklad:

$2^{60} (mod 13)$

$2^{4} = 16 \equiv 3$

$2^{6} = 2^{4} * 2^{2} \equiv 3 * 4 \equiv 12 \equiv -1$

$2^{60} = (2^{6})^{10} \equiv (-1)^{10} = 1$

Zbytek po dělení je tedy 1.

Děkuji

petrkovar · 04. 03. 2014 20:45

Doporučuji využít Malou Fermatovu větu: $a^p \equiv a \pmod{p}$ resp. $a^{p-1} \equiv 1 \pmod p$ .

hipot · 05. 03. 2014 13:21 — Editoval hipot (10. 03. 2014 20:42)

↑ petrkovar:
Diky, toto hezky funguje na ten příklad kdy výsledek má být 1.
$2^{60}(mod 13)$
$2^{12} \equiv 1 (mod 13)$
podle
$a^{p - 1} \equiv 1 (mod p)$
kde p je prvnočíslo
$(2^{12})^{5} = 2^{60}$
$1^{5} = 1$
Tudíž zbytek je 1

Ale nedaří se mi to aplikovat znovu na jiné čísla:
$7^{30} (mod13)$
Kde výsldek by měl být 12 podle kalkulačky.
$7^{12} \equiv 1 (mod13)$
Nicméně mocněním 12 neposkládám zpět původní číslo.
Rozhodl jsem se jít jinou cestou:
$7^{13} \equiv 7 \equiv -6 (mod13)$
podle
$a^{p} \equiv a (mod p)$
Kde p je prvočíslo
$7^{13} * 7^{2} \equiv -6 * 49$
$7^{15} \equiv -294 \equiv -8$
Nyní jsem chtěl získat původní číslo $7^{30}$
Umocil jsem v dobré víře poslední řádek na druhou, ale zbytky po dělení se následně začaly lišit.
$(7^{15})^{2} \equiv -8^{2}$
Toto už neplatí.

V čem prosímvás dělám chybu?
Děkuji

petrkovar · 08. 03. 2014 21:40

Proč by to nemělo platit?
$(-8)^2 = +64 \equiv 12 \equiv -1 \pmod{13}$ .

Já bych využil malou Fermatovu větu takto:
$7^{30} \equiv 7^6 \pmod{13}$ , protože $7^{24} = (7^{12})^2 \equiv 1^2 = 1 \pmod{13}$ .
$7^6 = 49^3 \equiv (-3)^3 = -27 \equiv -1 \pmod{13}$ .

hipot · 10. 03. 2014 10:44 — Editoval hipot (10. 03. 2014 20:34)

↑ petrkovar:
Děkuji, ale uplně tomu nerozumím.
Na tom mém příkladu nefongovalo to poslední, přes to, že jsem si myslel, že získat původní číslo umocněním by nemělo nic pokazit.

K tomu vašemu postupu:
Jak jste zjistil, že $7^{30}\equiv 7^{6}$ ? Protože $6=24:4$ ? a $24$ vznikne vynásobením exponentů $(^{12})^{2}$ a kde $7^{12}\equiv 1$ podle Fermatovy věty?
Potom ale nechápu, jaktože umocnění ve vašem případě nevadilo a v mém ano.
Protože u mě $(7^{15})^{2} neni\equiv -8^{2}$ i když o řádek výše to ještě fungovalo.

Mohl byste prosím popsat ty krotky podrobněji, jak postupujete? Já vím, že je to hodně psaní v LaTeXu, a že vám to příjde zřejmé, ale mě ne. :)

Děkuji.

petrkovar · 10. 03. 2014 12:39

↑ hipot:
$7^{30}\equiv 7^{6}$ , protože $7^{30} = 7^{24+6}$ a $7^{24} = (7^{12})^2 \equiv 1^2 = 1 \pmod{13}$ , tedy $7^{30} \equiv 1 \cdot 7^6$ . Vašemu kombinačnímu číslo nerozumím.

Co se nerovnosti po umocnění týká, neudělal jste chybu jenom ve znaménku?
$(-8)^2 = +64$ ale $-8^2=-64$ ?

hipot · 10. 03. 2014 20:32

↑ petrkovar:
Ano udělal jsem chybu. Už mi to vychází.
Děkuji za rady, s tímto už bych to snad měl být schopen pochopit.

To není kombinační číslo, ale nepovedený pokus o demonstraci "něco na dvanáctou na druhou" což dohromady dá číslo 24.

Pošlu vašemu foru dárcovskou SMS. :)

Matematické Fórum

#1 03. 03. 2014 17:36 — Editoval hipot (03. 03. 2014 17:36)

Výpočet zbytku po dělení velkého čísla pomocí kongruence

#2 04. 03. 2014 20:45

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

#3 05. 03. 2014 13:21 — Editoval hipot (10. 03. 2014 20:42)

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

#4 08. 03. 2014 21:40

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

#5 10. 03. 2014 10:44 — Editoval hipot (10. 03. 2014 20:34)

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

#6 10. 03. 2014 12:39

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

#7 10. 03. 2014 20:32

Re: Výpočet zbytku po dělení velkého čísla pomocí kongruence

Zápatí