Beste antwoord
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
sinds 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Antwoord
Je zou gewoon een computer kunnen opstarten en het vragen, en ik kreeg 1091132094649, maar je moet bedoelen, hoe kan dit worden gedaan met een minimum aan potlood en papier, of hoe kan een veel groter probleem worden opgelost op een computer zonder extravagant gebruik van CPU-cycli.
Waarschijnlijk willen hiervoor de Chinese reststelling. 20 = 2 ^ 2 * 5, dus 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Dus wat is 3 ^ 30 mod 5 ^ 10? Werk in basis 5 rekenkunde. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, vermenigvuldig nu met 3 ^ 3 = 102, maar VERWIJDER alle cijfers voorbij de 10e macht van 5: 12133131112 trimt tot 2133131112. Maak dit ten slotte vierkant uit, terwijl je alles boven de 10e macht van 5 weggooit terwijl je bezig bent: 4304012044. Basis 10, om terug te keren naar het vertrouwde terrein, dit is 9047774.
Nu wil je 3 ^ 30 mod 2 ^ 20. Dezelfde oefening, maar deze keer werk je in binair formaat. Je leert uiteindelijk dat het 686265 mod 2 ^ 20 is.
Nu is het tijd voor de Chinese reststelling. Dit zegt dat gegeven twee relatief primaire moduli, hier 2 ^ 20 en 5 ^ 10, en congruentiecondities mod elk, hier dat het antwoord 9047774 mod de eerste en 686265 mod de andere is, er een unieke n is tussen 0 en het product van jouw moduli, minder 1. En je vindt het via het idee dat als n = a mod p en b mod q, dan n = a + pk dus (a + pk) = b mod q. dus pk = (b-a) mod q, dus k = (inverse van p) * (b-a) mod q. En de inverse van p mod q wordt gevonden met het uitgebreide Euclidische algoritme. (Je extraheert de ggd van p en q, wetende dat het uiteindelijk 1 zal zijn, maar houd bij wat je leert over s * p + t * q = kleiner en kleiner, totdat je s * p + t * q = 1 en dan is s het omgekeerde van p mod q.)