Bedste svar
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 fyre en computer op og spørge den, og jeg fik 1091132094649, men du må betyde, hvordan kan dette gøres med et minimum af blyant- og papirarbejde, eller hvordan kan der gøres et meget større problem på en computer uden ekstravagant brug af CPU-cyklusser.
Du sandsynligvis ønsker den kinesiske restsætning for dette. 20 = 2 ^ 2 * 5, så 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Så hvad er 3 ^ 30 mod 5 ^ 10? Arbejd i basisregning. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, gang nu med 3 ^ 3 = 102, men KASSER alle cifre ud over den 10. effekt af 5: 12133131112 trimmer til 2133131112. Endelig kvadrat dette ud, kasser alt over den 10. styrke på 5, mens du går: 4304012044. Base 10, for at komme tilbage til velkendt græs, er dette 9047774.
Nu vil du have 3 ^ 30 mod 2 ^ 20. Samme øvelse, men denne gang arbejder du i binær. Du ender med at lære, at det er 686265 mod 2 ^ 20.
Nu er det tid til den kinesiske restsætning. Dette siger, at givet 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 anden, er der en unik n mellem 0 og produktet af din moduli, mindre 1. Og du finder 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 = (omvendt af p) * (b-a) mod q. Og det omvendte af p mod q findes med den udvidede euklidiske algoritme. (Du udtrækker gcd af p og q, idet du ved godt, at det bliver 1 til sidst, men holder styr på, hvad du lærer om s * p + t * q = mindre og mindre, mens du går, indtil du får s * p + t * q = 1 og derefter er s det omvendte af p mod q.)