Generell metod för att beräkna stora tal med modulo?

Hej!

Jag försöker beräkna stora tal med modulo, men jag har ingen aning om hur jag ska gå tillväga för att lösa uppgifter av det här stuket:

5^327 mod 17
5^1111 mod 12
3^41 mod 79
4^220 mod 19

Jag är alltså inte ute efter enbart svaret, utan tankegången bakom lösningsmetoden!

Tack på förhand,
Jaylink

Om det är själva det numeriska resultatet du är intresserad av så prova http://www.wolframalpha.com/

T ex http://www.wolframalpha.com/input/?i=5%5E1111+mod+12

Annars finns ju Wikipedia, men det har du väl redan tittat på ... https://en.wikipedia.org/wiki/Modulo_operation Det kan nog vara en bra startpunkt annars.

Nej, vad jag är intresserad av är själva tankebanan som (vad jag kan se?) inte går att få på Wolfram Alpha. Jag hittar ej heller någon lösningsmetod för uppgifter av det slaget jag skrev på Wikipedia heller.

Tror inte det finns någon enkel generell lösningsmetod om man ska räkna för hand. Däremot i vissa specialfall kan man hitta lösningar som går snabbt att räkna för hand (tillrättalagda matteproblem). Annars är det nog mer eller mindre bra dataalgoritmer man får använda.

Här är ytterligare en Wikipedia sida som kanske kan vara av intresse: https://en.wikipedia.org/wiki/Modular_exponentiation

Uppgifterna kommer från min mattebok som det är meningen att vi ska räkna utan några hjälpmedel alls. Tyvärr saknas det exempel på den här sortens uppgifter, och därför hoppas jag att någon annan ska kunna hjälpa mig.

En viktig regel är att om x ~ y så gäller x^n ~ y^n.
T.ex. gäller 25 ~ 1 (mod 12) varför 5^1111 = 5 · (5^2)^555 ~ 5 · 1^555 = 5 · 1 = 5.

Man kan även använda Fermats lilla sats: a^(p-1) ~ 1 (mod p) om p är ett primtal.
T.ex. gäller 5^16 ~ 1 (mod 17) varför 5^327 = (5^16)^20 · 5^7 ~ 1^20 · 5^7 = 5^7.

Den första uppgiften förstår jag, tack så mycket. I en annan tråd skrev du följande lösning på uppgiften 3^41 mod 79

3^41 = 3 · (3^4)^10 = 3 · 81^10 ≡ 3 · 2^10 = 3 · 1024 = 3072 ≡ 70 (mod 79)

Jag hänger med stegen hela vägen fram tills det sista, där du får att 3072 ≡ 70 (mod 79). Hur vet du att det är svaret? Vad är syftet med alla omskrivningar?

Syftet med alla omskrivningar är att genom steg som inte förändrar resten modulo 79 reducera ett stort tal till ett mindre där det genom vanlig aritmetik är enkelt att beräkna resten modulo 79.


Eftersom 3^41 = 3 · (3^4)^10 = 3 · 81^10 har 3^41 och 3 · 81^10 samma rest modulo 79.

Sedan gäller att 81 har resten 2 modulo 79, samt regeln att om x och y har samma rest modulo k så har x^n och y^n samma rest modulo k. Därför gäller att 81^10 och 2^10 har samma rest modulo 79, vilket medför att 3 · 81^10 och 3 · 2^10 har samma rest modulo 79.

Därefter används vanlig aritmetik ett par steg igen:
3 · 2^10 = 3 · 1024 = 3072

Slutligen, efter att ha utfört en heltalsdivision av 3072 med 79 och fått resten 70, drar jag slutsatsen att 3^41 har resten 70 modulo 79.

Tack så jättemycket, du räddade nog precis min tenta imorgon!