Hitta rest av ett tal med stor exponent? (Modulo)

2014-11-12, 14:51

#13

Medlem

Reg: Jun 2013

Inlägg: 7 359

Citat:

Ursprungligen postat av Mattelisa

Tack för all hjälp!

Jag förstår helheten, och vad man är ute eftter, men inte hur man "vet" att:
16^9 * 4 är kongruent (mod 5) med 1^9 * (-1)

Det är en upprepad tillämpning av regeln

a==b (mod n) och c==d (mod n) => ac==bd (mod n).

I det här fallet

16==1 (mod 5) => 16²==1² (mod 5) => 16³==1³ (mod 5) ... =>

16⁹==1⁹ (mod 5)

Den sista kongruensen kombineras med 4==-1 (mod 5) och ger

16⁹*4==1⁹*(-1) (mod 5)

Citera

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback

Swish: 123 536 99 96 Bankgiro: 211-4106