Legjobb válasz
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
mivel 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Válasz
Csak fel lehetne kapcsolni egy számítógépet és megkérdeznénk, és én got 1091132094649, de meg kell értenie, hogyan lehet ezt megtenni minimális ceruzával és papírral végzett munkával, vagy hogyan lehetne egy sokkal nagyobb problémát megoldani egy számítógépen anélkül, hogy extravagáns CPU-ciklusokat használnának.
Valószínűleg akarja a kínai fennmaradó tételt ehhez. 20 = 2 ^ 2 * 5, tehát 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Tehát mi a 3 ^ 30 mod 5 ^ 10? Dolgozzon az 5. alap számtanában. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, most szorozzuk meg 3 ^ 3 = 102-vel, de az 5-ös szám 10-edikén túlmutató összes számot eldobjuk 2133131112-ig. ki, eldobva az 5-ös 10. teljesítménye fölött mindent, ahogy haladsz: 4304012044. A 10. alap, hogy visszatérjünk az ismert gyepre, ez a 9047774.
Most 3 ^ 30 mod 2 ^ 20-at akarsz. Ugyanaz a fúró, de ezúttal binárisan dolgozik. Végül megtudja, hogy 686265 mod 2 ^ 20.
Itt az ideje a kínai maradék tételnek. Ez azt mondja, hogy két viszonylag elsődleges modul, itt 2 ^ 20 és 5 ^ 10, és a kongruenciafeltételek mindegyike mod, itt a válasz 9047774 mod az első és a 686265 mod a másik, akkor egyedi n van 0 és 0 szorzata között modulja, kevesebb 1. És azt az ötleten keresztül találja meg, hogy ha n = a mod p és b mod q, akkor n = a + pk tehát (a + pk) = b mod q. tehát pk = (b-a) mod q, tehát k = (p inverze *) (b-a) mod q. A p mod q inverzét pedig a kiterjesztett euklideszi algoritmussal találjuk meg. (Kivonja a p és q gcd-jét, jól tudva, hogy a végén 1 lesz, de nyomon követheti, hogy mit tanul s * p + t * q = egyre kisebb, ahogy megy, amíg meg nem kapja s * p + t * q = 1, majd s a p mod q inverze.)