Beste Antwort
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
seit 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Antwort
Sie könnten einfach einen Computer starten und ihn fragen, und ich Ich habe 1091132094649, aber Sie müssen meinen, wie dies mit einem Minimum an Bleistift- und Papierarbeit geschehen kann oder wie ein viel größeres Problem auf einem Computer ohne extravagante Verwendung von CPU-Zyklen gelöst werden kann.
Sie wahrscheinlich will den chinesischen Restsatz dafür. 20 = 2 ^ 2 * 5, also 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Was ist also 3 ^ 30 mod 5 ^ 10? Arbeiten Sie in Basis 5 Arithmetik. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, jetzt mit 3 ^ 3 = 102 multiplizieren, aber alle Ziffern jenseits der 10. Potenz von 5: 12133131112 auf 2133131112 abschneiden Verwerfen Sie alles, was über der 10. Potenz von 5 liegt, während Sie gehen: 4304012044. Basis 10, um zum vertrauten Rasen zurückzukehren, ist dies 9047774.
Jetzt möchten Sie 3 ^ 30 mod 2 ^ 20. Gleicher Drill, aber diesmal arbeiten Sie in Binärform. Am Ende erfahren Sie, dass es sich um 686265 Mod 2 ^ 20 handelt.
Jetzt ist es Zeit für den chinesischen Restsatz. Dies besagt, dass bei zwei relativ primären Modulen, hier 2 ^ 20 und 5 ^ 10, und Kongruenzbedingungen mod jeweils mod, hier, dass die Antwort 9047774 mod der erste und 686265 mod der andere ist, es ein eindeutiges n zwischen 0 und dem Produkt von gibt Ihre Module, weniger 1. Und Sie finden es über die Idee, dass wenn n = a mod p und b mod q, dann n = a + pk, also (a + pk) = b mod q. also pk = (b-a) mod q, also k = (invers von p) * (b-a) mod q. Und die Umkehrung von p mod q wird mit dem erweiterten euklidischen Algorithmus gefunden. (Sie extrahieren die gcd von p und q, wobei Sie genau wissen, dass es am Ende 1 sein wird, aber verfolgen Sie, was Sie über s * p + t * q = immer kleiner werden, bis Sie s * erhalten. p + t * q = 1 und dann ist s die Umkehrung von p mod q.)