Meilleure réponse
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
depuis 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Réponse
Vous pouvez simplement allumer un ordinateur et le demander, et je obtenu 1091132094649, mais vous devez dire, comment cela pourrait-il être fait avec un minimum de crayon et de papier, ou comment un problème beaucoup plus important pourrait-il être résolu sur un ordinateur sans utilisation extravagante des cycles du processeur.
Vous êtes probablement veulent le théorème du reste chinois pour cela. 20 = 2 ^ 2 * 5, donc 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Alors, quest-ce que 3 ^ 30 mod 5 ^ 10? Travaillez en arithmétique en base 5. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, multipliez maintenant par 3 ^ 3 = 102, mais en REJETANT tous les chiffres au-delà de la 10e puissance de 5: 12133131112 sajuste à 2133131112. Enfin carré ceci au-delà de la 10e puissance de 5 au fur et à mesure: 4304012044. Base 10, pour revenir au terrain familier, cest 9047774.
Maintenant, vous voudrez 3 ^ 30 mod 2 ^ 20. Même exercice, mais cette fois, vous travaillez en binaire. Vous finissez par apprendre qu’il s’agit du 686265 mod 2 ^ 20.
Il est maintenant temps pour le théorème du reste chinois. Cela dit que, étant donné deux modules relativement premiers, ici 2 ^ 20 et 5 ^ 10, et des conditions de congruence mod chacun, ici que la réponse est 9047774 mod le premier et 686265 mod lautre, il y a un n unique entre 0 et le produit de vos modules, moins 1. Et vous le trouvez via lidée que si n = a mod p et b mod q, alors n = a + pk so (a + pk) = b mod q. donc pk = (b-a) mod q, donc k = (inverse de p) * (b-a) mod q. Et linverse de p mod q est trouvé avec lalgorithme euclidien étendu. (Vous extrayez le pgcd de p et q, sachant très bien que ce sera 1 à la fin, mais en gardant une trace de ce que vous apprenez sur s * p + t * q = de plus en plus petit, au fur et à mesure, jusquà ce que vous obteniez s * p + t * q = 1 et alors s est linverse de p mod q.)