Citat:
Ursprungligen postat av starke_adolf
Fråga hur min lärare tänkte när han gjorde det här i diskret matematik:
Är detta sant eller falskt? 13^242 ≡ 26 (mod 143) [143 = 11 * 13]
"Ja, 120 = 10 * 12
241 ≡ 1 (mod 120)
så 13^241 ≡ 13 (mod 143)
och 13 * 13 = 169 ≡ 26 (mod 143)"
Först och främst; vad i hela helvete får han 241 från? Det står 13^242 i uppgiften. I sammanhanget (som jag inte förstått) kan jag ändå förstå varför han försöker hitta en multipel, 120, i 241 som i dess modulo ger rest 1 eftersom alla potenser av det också blir 1 men här känns det bara lösryckt. Äh, det är ingen idé att skriva allt jag inte förstår, ni kan nog förklara! Om inte, visa hur ni skulle ha löst det. Tack!
Ett enkelt sätt att lösa sådana uppgifter är att gå "nedifrån" bland exponenter ända upp till den sökta.
Först börjar man med att undersöka vilka exponenter man vill veta, detta på följande vis:
Är exponenten jämn halverar du den, är exponenten udda tar du bort 1. Fortsätt tills du har 1 kvar.
I detta fall får vi listan: 242, 121, 120, 60, 30, 15, 14, 7, 6, 3, 2, 1. Nu testar vi för dessa värden n_i vad 13^n_i är i tur och ordning nedifrån. Går man 1 uppåt multiplicerar vi med 13, dubblar vi exponenten kvadrerar vi resten.
13^1=13, uppenbarligen. 13^2=169=26, 26(=13^2)*13=13^3=52, 52^2=-13 ....
Till slut får vi 13^242 och får reda på vad det är.