Matematické Fórum

Dworzaaa · 02. 01. 2010 03:44

http://pavel.klavik.cz/vyuka/lingebra/lauk3.pdf

Mohl by prosim nekdo ukazat nebo napsat postup, jak se resi takove priklady? Diky.

lukaszh · 02. 01. 2010 10:35

↑ Dworzaaa:
Ten prvý má byť asi $2^{2009}$ . Musíš nájsť zvyšok r modulo 2. Teda riešiš kongruenciu

Výsledok je 2.

Marian · 02. 01. 2010 11:44 — Editoval Marian (02. 01. 2010 11:50)

↑ Dworzaaa:
Zbytek je také snadný. Ukáži, jak to provést.

Ad 2.
V případě, že není exponent prvočíslo (tento případ), lze se pokusit o vhodné "vypůjčení" některého činitele rozkladu, kt. aplikujeme pomocí částečného umocnění na základ exponenciály (zde dvojka). Svou roli hraje i hodnota modulu, dle kterého posuzujeme takovou mocninu. Uvědomíme-li si, že platí 2^2=4=1*3+1, je věc jasná. Snažíme se totiž zapsat částečně umocněné číslo ve tvaru násobek hodnoty modulu+relativně malé číslo (výhrou je, když je to jednička).

Ad 3.
Zde je oproti případu 2 problém v tom, že v exponentu je prvočíslo, tj. 67. V takovém případě dobře slouží malá Fermatova věta. Platí totiž (podle této věty) $4^{7-1}\equiv 1\quad (\text{mod}\, 7)$ , což je totéž jako $4^6\equiv 1\quad (\text{mod}\, 7)$ . Umocněním na jedenáctou máme $4^{66}\equiv 1\quad (\text{mod}\, 7)$ . Násobíme-li navíc čtyřkou, je konečně $4^{67}\equiv 4\quad (\text{mod}\, 7)$ .