Beste svaret
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
siden 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Svar
Du kan bare skyte på en datamaskin og spørre den, og jeg fikk 1091132094649, men du må mene hvordan dette kan gjøres med et minimum av blyant- og papirarbeid, eller hvordan kan det gjøres et mye større problem på en datamaskin uten ekstravagant bruk av CPU-sykluser.
Du sannsynligvis vil ha den kinesiske restsatsen for dette. 20 = 2 ^ 2 * 5, så 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Så hva er 3 ^ 30 mod 5 ^ 10? Arbeid i base 5-aritmetikk. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, multipliser nå med 3 ^ 3 = 102, men KASSER alle sifrene utover den 10. kraften i 5: 12133131112 trimmer til 2133131112. Endelig kvadrat dette ut, kaste alt over 10. kraft på 5 mens du går: 4304012044. Base 10, for å komme tilbake til kjent gress, er dette 9047774.
Nå vil du ha 3 ^ 30 mod 2 ^ 20. Samme øvelse, men denne gangen jobber du i binær. Du ender opp med å lære at det er 686265 mod 2 ^ 20.
Nå er det på tide for den kinesiske restsatsen. Dette sier at gitt to relativt primære moduler, her 2 ^ 20 og 5 ^ 10, og kongruensbetingelser mod hver, her at svaret er 9047774 mod den første og 686265 mod den andre, er det en unik n mellom 0 og produktet av modulene dine, mindre 1. Og du finner det via ideen om at hvis n = a mod p og b mod q, så n = a + pk så (a + pk) = b mod q. så pk = (b-a) mod q, så k = (invers av p) * (b-a) mod q. Og det omvendte av p mod q er funnet med den utvidede euklidiske algoritmen. (Du trekker ut gcd av p og q, vel vitende om at det blir 1 til slutt, men holder rede på hva du lærer om s * p + t * q = mindre og mindre, mens du går, til du får s * p + t * q = 1 og deretter er s det omvendte av p mod q.)