# zap. pisemka 20.12. - problem

<{ForumPost(poster="Myshaak", timestamp=2007-12-20 16:22:49)}>
Zdar, mam jeden problem v dnesni zapoctove pisemce od Sarocha. (Stacilo mi ziskat cca 1,5 bodu z 10, takze podle toho vypadala moje "priprava" :) ) Problem nastal u prikladu 3:  
  
(3) Spoctete posledni dve cifry cisla 31^(32^33). Napoveda: ve vhodne chvili muze pomoci spocitat zbytky po deleni 20, resp. 25.  
  
Nevite nekdo jak na to? Mne ta napoveda moc nepomohla... :(  
Kdyz jsem jel striktne podle algoritmu, co jsme delali:  
  
pocitam vlastne to cislo mod 100 .... Fi(100)=40, NSD(100,31)=1, fajn, takze 31^40 = 1  mod 100  
... ted tedy chci pocitat 32^33 mod 40 ... Fi(40)=4*4=16, NSD(32,40)!=1, takze jsem v haji... :/  
... kejkleni s 20 nebo 25 moc nepomohly...  
... teda akorat 32^33 mod 25 slo spocitat: Fi(25)=20, NSD(25,32)=1, fajn, 32^20 = 1  mod 25  
... ... ale 32 je vlaste 7 -> a 7^2 je 49 neboli (-1) ----> 32^33 = 7^33 = (7^2)^16 * 7 = 7 mod 25  
... ... Ale to mi pomuze???  
  
anybody help? :)  
  
Jo, kdyz uz jsem u toho, tak pro ouplnost zbytek pisemky, byla celkem lehka, teoreticky jsem mohl odejit po 10 minutach... ;)  
  
(1) Nakreslete Hassuv diagram svazu kongruenci grupy (Z<sub>875</sub>,+,-,0). (1,5b)  
(2) --"--    nejakeho konecneho svazu, ktery neni generovan zadnymi svymi ctyrmi (a mene) prvky. (1b)  
(3) viz vyse (2b)  
(4) Slovni uloha. Cinsti generalove pocitali vojaky tak, ze je nechali nastupovat do n-stupu. Pocet vojaku pak spocitali z toho, kolik jim pri ruznych nastupech vojaku prebylo. General mel pred bitvou 1200 vojaku. Po bitve nechal zbyle nastoupit do rad po peti a videl, ze zbyli tri. Pak po sesti - opet zbyli tri, po sedmi - zbyl jeden. Nakonec po jedenacti - zadny nezbyl. Kolik generalovych vojaku prezilo bitvu? (2b)  
(5) Kolik prvku ma mnozina { (x,y), 0<x,y<=48 & x^28 + xy + y^29 = 2   mod 29  } (2b)  
(6) Bonus. Bud R konecny komutativni okruh. Oznacime R* := {r z R; (existuje s z R tz. r.s = 1)}. Overste, ze R* spolus operaci nasobeni tvori grupu. Dale dokazte, ze ma-li R* lichy pocet prvku, potom plati pro kazde x : x+x=0. (1,5b)
<{/ForumPost}>

<{ForumPost(poster="MIKI", timestamp=2008-01-02 14:43:10)}>

 > Myshaak wrote:Zdar, mam jeden problem v dnesni zapoctove pisemce od Sarocha. (Stacilo mi ziskat cca 1,5 bodu z 10, takze podle toho vypadala moje "priprava" :) ) Problem nastal u prikladu 3:  
 >   
 > (3) Spoctete posledni dve cifry cisla 31^(32^33). Napoveda: ve vhodne chvili muze pomoci spocitat zbytky po deleni 20, resp. 25.  
 >   
 > Nevite nekdo jak na to? Mne ta napoveda moc nepomohla... :(

No ja by som to robil asi nasledovne pocitanim v Z100:  
(za spravnost nerucim bo nejak nemam kalkulajdu :))  
ked si to rozmyslis pripocitavas vlastne 30 a orezavas (mod 100).  
31 (31^1), 61 (31*31), 91 (61*31), 21 (91*31), 51 (21*31), 81, 11, 41, 71, 1 (tu sa ti to zacne cyklit)  
z tohoto dostanes, ze po 31^10 budes mat zbytok 1 takze po 31^30 to bude tiez 1 a po 31^32 to bude 61.  
a opakujes totozny postup (pripocitavas 60 a orezavas):  
61 (61^1), 21 (61*61), 81, 41, 1  
z tohoto  zase dostanes, ze po 61^5 budes mat zbytok 1 takze po 61^30 to bude tiez 1 a po 61^33 to bude 81 co je pozadovany vysledok pokial som sa nesekol.  
  
// edit  
dalsie riesenie je si spravit toto:   
31, 61, 91, 21, 51, 81, 11, 41, 71, 1  
vies ze mas pocitat:  
(31*31*...*31) mod 100 = ?  
pocet 31-tiek je 32*33=1056  
vies ze po 10-tich sa dostanes na 1. takze:  
1056 mod 10=6  
a pozries sa do "postupnosti" zbytkov a najdes 6-ty  "prvok" t.j 81.  
  
Stastny novy rok ;)
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2008-01-02 16:51:33)}>
Hmmm, diky! Urcite zajimava myslenka! :)  
Jen si nejsem jist jednou veci, v tom zadani je **31^(32^33)** a mne prijde, jako bys resil **31^(32*33)**... :) Ale to neva, v nejhorsim pripade se je aspon od ceho odpichnout! ;)  
  
**EDIT**: Joo, vlastne to potom vubec neni slozity ... vim, ze 31 se opakuje s periodou 10, takze vlastne chci zjistit 32^33 mod 10. No a 32 =<sub>10</sub> 2.  
dostanu 2 -> 4 -> 8-> 6 -> 2 -> atd. ... takze 32<sup>4k</sup> = 6 mod 10 // pripadne se to posune   
-takze 32<sup>32</sup> by taky melo byt 6 ... no a na 33. tedy 2  
...zbytek uz by mel byt easy :)  
  
(Nejsem si tim resenim ted ouplne jisty, spravny vysledek -snad i s postupem- se dozvim dnes)
<{/ForumPost}>

<{ForumPost(poster="MIKI", timestamp=2008-01-03 21:19:51)}>

 > Myshaak wrote:
 > Jen si nejsem jist jednou veci, v tom zadani je **31^(32^33)** a mne prijde, jako bys resil **31^(32*33)**... :) Ale to neva, v nejhorsim pripade se je aspon od ceho odpichnout! ;)

Ups. :D    
Uz ani citat neviem.  :roll:  
  
Tak to by potom nejak malo ist cez malu Fermatovu vetu, ci ako sa to vola.  :idea:
<{/ForumPost}>