Matematické Fórum

drabi · 24. 10. 2012 20:59

Ahoj, mám problém s domácím úkolem. Nejsem si jistá, zda postupuju správně, tak jsem se chtěla zeptat, zda by mi někdo, prosím, nezkontroloval můj postup, případně mě opravil.

Mám najít poslední dvě cifry čísla $2012^{2011^{2010^{2009^{2008}}}}$

$2009^{2008} \text{mod} 100$
jelikož $\text{NSD}(2009,100) = 1, \varphi(100)=40$ použiju Eulerovu větu, takže
$2009^{2008} \text{mod} 100 = 2009^{2008 \text{mod} 40} = 2009^8 \text{mod} 100 = 9^8 \text{mod} 100 = 21$

jelikož $\text{NSD}(2010,100) <>1$ tak jsem pokračovala až druhou dvojicí, nenapadla mě žádná vhodná substituce nebo dělení

$2011^{2010} \text{mod} 100$
jelikož $\text{NSD}(2011,100) = 1, \varphi(100)=40$ opět použiju Eulerovu větu, takže
$2011^{2010} \text{mod} 100 = 2011^{2010 \text{mod} 40} = 2011^10 \text{mod} 100 = 11^10 \text{mod} 100 = 1$

takže mám $2012^{2011^{2010^{2009^{2008}}}} \text{mod} 100 = 2012^{1^{21}} \text{mod} 100 = 2012 \text{mod} 100 = 12$

Díky za případné tipy a nápady:)

drabi · 24. 10. 2012 21:36

↑ Tomas.P:
Díky za odkaz. Leč nejsem si jistá, že tak můžu postupovat, pokud mám ta čísla soudělná, což v odkazu není.
Na přednášce jsme si ukazovali, že to nejde, že si musíme nějak vhodně zasubstituovat a zkrátit to, ale v těchhle mocninách to nějak nevidím. Mohl bys mi s tím prosím trochu pomoct?

Tomas.P · 24. 10. 2012 22:10

↑ drabi:
Za pokus to stálo :-)

Bati · 25. 10. 2012 11:12

Ahoj,
zdá se mi, že postupuješ poněkud obráceně:)
Nejprve bych si uvědomil, že $\text{NSD}(2012,100)=4$ , tedy bych pak řešil kongruenci $503^{2011^{2010^{2009^{2008}}}}\cdot4^{2011^{2010^{2009^{2008}}}-1}\equiv\frac{x}4\mod25$
Teď už bych použil eulerovu větu třeba na $503^{2011^{2010^{2009^{2008}}}}\equiv503^{2011^{2010^{2009^{2008}}}\mod\varphi(25)}\mod25$ a tak dál...

drabi · 25. 10. 2012 14:01

↑ Bati:
no právě, že to a tak dál, mi není moc jasné.. jak to potom udělat s tím -1. Nedá se to nějak obejít?

drabi · 25. 10. 2012 14:20

tak zkouším to, ale nevím, zda je to ok, můžeš mi to prosím zkontrolovat?
$x = 4y$
$503^{2011^{2010^{2009^{2008}}}}\cdot4^{2011^{2010^{2009^{2008}}}-1}\equiv y \mod25$

řeším tedy $503^{2011^{2010^{2009^{2008}}}}\equiv503^{2011^{2010^{2009^{2008}}}\mod\varphi(25)}\mod25$

takže jelikož NSD(503,25) = 1 tak nas zajima $2011^{2010^{2009^{2008}}}\mod 20$
opět NSD(2011,20)=1 takže nas zajima $2010^{2009^{2008}}\mod \varphi(20)$
tady NSD(2010,8)=2 takže provedu substituci y=2z a rozpadne se mi to na
$1005^{2009^{2008}}\cdot2^{2009^{2008}-1}\equiv z \mod 4$
pokračuju s tím: $1005^{2009^{2008}}\equiv z \mod 4$
NSD(1005,4)=1, $\varphi(4)=2$
takze mi zbyva vyresit $2009^{2008} \mod 2 = 1$

pak nam zbyva jeste
$2^{2009^{2008}-1}\equiv z \mod 4$ a tady si nejsem jista jak to udelat.. potom se taky musim vratit k te prvni casti a to je pro me obdobny problem..

drabi · 25. 10. 2012 15:08

$2^{2009^{2008}-1} \mod 4 = 0$
ale jak potom to dát dohromady?
když mám toto:
$1005^{2009^{2008}}\cdot2^{2009^{2008}-1}\equiv z \mod 4$
a zjistila jsem, že $1005^{2009^{2008}} \equiv 1 \mod 4$ a $2^{2009^{2008}-1}\equiv 0 \mod 4$
pak celkově to dává (???), že $503^{2011^{2010^{2009^{2008}}}}\equiv 0 \mod25$
Nedává mi to smysl

Bati · 25. 10. 2012 22:35

Už v kroku $2010^{2009^{2008}}\mod \varphi(20)$ ses měla zarazit, protože číslo 2010 je dělitelné dvěma, takže nějaká jeho gigantická mocnina je určitě dělitelná osmi. Tudíž zbytek po dělení je 0 a vrátíš se o krok zpátky. Víš teď totiž, že $2011^{2010^{2009^{2008}}}\equiv2010^0=1\mod 20$ . A zase se vrátíš o jeden krok:
$503^{2011^{2010^{2009^{2008}}}}\equiv503^1\equiv3\mod25$

Co se týče mocniny té čtyřky, tam jsem použil malý trik. Nejdřív použiju normálně eulerovu větu a zajímám se tedy o $2011^{2010^{2009^{2008}}}-1\mod20$ . Teď použiju vzorec pro $a^n-b^n$ a snadno zjistím, že to číslo je dělitelné 20, takže dává zbytek 0. Tím je ten příklad skoro vyřešený.