Nejlepší odpověď
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
od 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Odpověď
Stačí spustit počítač a zeptat se ho, a já dostal 1091132094649, ale musíte mít na mysli, jak by to mohlo být provedeno s minimem práce s tužkou a papírem, nebo jak by bylo možné udělat mnohem větší problém na počítači bez extravagantního použití cyklů CPU.
Pravděpodobně Chci za to čínskou větu o zbytku. 20 = 2 ^ 2 * 5, takže 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Co je tedy 3 ^ 30 mod 5 ^ 10? Pracujte v základní 5 aritmetice. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, nyní vynásobte 3 ^ 3 = 102, ale VYLOUČENÍ všech číslic nad 10. mocninu 5: 12133131112 ořízne na 2133131112. Nakonec to zaokrouhlete out, discarding everything above the 10 power of 5 as you go: 4304012044. Base 10, to get back to famous turf, this is 9047774.
Nyní budete chtít 3 ^ 30 mod 2 ^ 20. Stejný nácvik, ale tentokrát pracujete v binárním formátu. Nakonec se dozvíte, že je to 686265 mod 2 ^ 20.
Nyní je čas na čínskou větu o zbytku. To říká, že vzhledem k tomu, že dva relativně primární moduly, zde 2 ^ 20 a 5 ^ 10, a podmínky shody mod každý, zde je odpověď 9047774 mod první a 686265 mod druhá, existuje jedinečné n mezi 0 a produktem vaše moduly, méně 1. A zjistíte to z myšlenky, že pokud n = a mod p a b mod q, pak n = a + pk tak (a + pk) = b mod q. takže pk = (b-a) mod q, takže k = (inverzní k p) * (b-a) mod q. A inverze p mod q se nalézá s rozšířeným euklidovským algoritmem. (Extrahujete gcd z p a q, protože dobře víte, že to bude nakonec 1, ale sledujte, co se dozvíte o s * p + t * q = menší a menší, jak jdete, dokud nedostanete s * p + t * q = 1 a potom s je inverzní k p mod q.)