Kongruensräkning - Beräkna 99^999999 (mod 23)
Uppgift:
Beräkna
Fråga:
Det som jag mest har problem med är de tre sista stegen (se lösning från facit nedan). På tentan i kursen som jag läser så är kalkylator ej ett tillåtet hjälpmedel så jag vänder mig till er för att kanske få tips på hur jag på ett smidigt och enkelt vis räknar ut de två sista stegen utan kalkylator? (Se lösning nedan)
Man kan förstås faktiskt räkna ut 7^11 och sedan dela med 23, men eftersom man bara ska arbeta mod 23 kan man göra det med mindre tal: Vi kvadrerar 7. Det blir 49. 49 mod 23 = 3 (om jag får skriva så). 7^11 = 7^(2*5+1) = 7*49^5 = 7*3^5 mod 23. Och så vidare.
Laguna skrev:Man kan förstås faktiskt räkna ut 7^11 och sedan dela med 23, /.../
Hur räknar du ut ett sådant tal på ett enkelt vis utan räknare? Min taktik känns inte så smidig men du kanske har en bättre strategi att dela med dig av. Jag skulle börja göra på följande vis:
/.../men eftersom man bara ska arbeta mod 23 kan man göra det med mindre tal: Vi kvadrerar 7. Det blir 49. 49 mod 23 = 3 (om jag får skriva så). 7^11 = 7^(2*5+1) = 7*49^5 = 7*3^5 mod 23. Och så vidare.
Den strategin röstar jag för :) Tack för hjälpen
Jag tänkte bara 49*7=243
243*7=nånting
*7=nånting
elva gånger
