Bonjour,
Je me demandais comment trouver le reste de la division de 1114 par 71.
J'ai bien appris à traiter les cas où la puissance est plus grande que le diviseur mais là je ne vois pas du tout.
Pour info le reste vaut 54 et il s'agit d'un exemple de test de primalité par la méthode de Lucas-Lehmer.
http://fr.wikipedia.org/wiki/Test_de...e_Lucas-Lehmer
Merci
Bonjour.
14=2*7.
modulo 71,donc
etc.
Cordialement.
Bonjour,
Merci pour la réponse.
Pourquoi basculer de 1114 à 507 ?
J'ai compris l'égalité mais pas pourquoi on le fait ni comment on continue.
Merci d'avance
Cela permet de diminuer la puissance, et donc de simplifier le calcul. Pour continuer, tu ne peux plus décomposer la puissance, tu peux décomposer 50, ce qui te donnera des puissances plus faciles à calculer.
If your method does not solve the problem, change the problem.
Ou plus généralement, on peut utiliser l'algorithme d'exponentiation rapide adapté pour les calculs modulaires :
14 = 8+4+2 = 2^3+2^2+2
Donc 11^14 = ((11^2)^2)^2 * (11^2)^2 * 11^2
11^2 = 121 = 50
11^2^2 = 50^2 = 2500 = 15
11^2^2^2 = 15^2 = 225 = 12
50*15 = 750 = 40
40*12 = 480 = 54
D’où 11^14 = 54
(tout les calculs étant fait modulo 71)
Merci beaucoup pour les réponses, c'est désormais très clair
