Cel mai bun răspuns
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
deoarece 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Răspuns
Ai putea să aprinzi un computer și să-l întrebi, iar eu am 1091132094649, dar trebuie să spui, cum s-ar putea face acest lucru cu un minim de creion și hârtie sau cum s-ar putea face o problemă mult mai mare pe un computer fără utilizarea extravagantă a ciclurilor CPU. vreau teorema restului chinez pentru asta. 20 = 2 ^ 2 * 5, deci 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Deci, ce este 3 ^ 30 mod 5 ^ 10? Lucrați în baza 5 aritmetică. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, acum se înmulțește cu 3 ^ 3 = 102, dar ELIMINând toate cifrele dincolo de puterea a 10-a de 5: 12133131112 trims la 2133131112. În cele din urmă pătrat acest afară, aruncând tot ce depășește puterea 10 a 5 pe măsură ce mergeți: 4304012044. Baza 10, pentru a reveni la gazonul familiar, acesta este 9047774.
Acum veți dori 3 ^ 30 mod 2 ^ 20. Același exercițiu, dar de această dată lucrați în binar. În sfârșit veți afla că este 686265 mod 2 ^ 20.
Acum este timpul pentru teorema chinezească a restului. Aceasta spune că, având în vedere doi moduli relativ primi, aici 2 ^ 20 și 5 ^ 10, și condițiile de congruență mod fiecare, aici că răspunsul este 9047774 mod primul și 686265 mod celălalt, există un n unic între 0 și produsul modulele tale, mai puțin 1. Și îl găsești prin ideea că dacă n = a mod p și b mod q, atunci n = a + pk deci (a + pk) = b mod q. deci pk = (b-a) mod q, deci k = (inversul lui p) * (b-a) mod q. Și inversul lui p mod q se găsește cu algoritmul euclidian extins. (Extrageți mcd-ul lui p și q, știind foarte bine că va fi 1 în final, dar urmărind ceea ce învățați despre s * p + t * q = din ce în ce mai mic, pe măsură ce mergeți, până când obțineți s * p + t * q = 1 și apoi s este inversul lui p mod q.)