Bonsoir, voici l'exercice pour lequel la rédaction me pose un problème :

Quel est le reste de la d.e de 57383^114 par 19.
57383 est congru à 3 (mod 19) (ce qui est laborieux à montrer sans calculette)
Puis Je chercher à me ramener à 1 ou -1 mod 19. Et c'est là que se pose le problème : quelle est la méthode générale à part le tâtonnement ? En effet, au début, j'ai chercher en parallèle les puissances de 3 et les multiples de 19 pour me ramener à une congruence souhaitée. J'ai abandonné à partir de 3^6. Je regarde les diverses corrections et je tombe sur : "3^9 congru à -1 (mod 19) ou encore des variantes comme 3^18 congru à 1 (mod19)". C'est beau, mais c'est parachuté et on sait pas d'où ça vient donc voici mes questions : faut-il trouver soit même ces sortes de "lemme" pour pouvoir résoudre le problème ? . Quelles sont les astuces et surtout comment-t-on quand le nombre est très grand ?? On va pas s'amuser à calculer toutes les puissances de 3 ???"
Se peut-il que l'on ne retombe jamais sur une congruence de 1 ou -1 (par exemple un nombre qui admet un reste périodique qui diffère de 1). Et alors comment on sait/quelle est la méthode pour pas trouver le reste par rapport au modulo n ?

Pas besoin de calculer des puissances de 3, tu regardes la suite des restes mod 19 :

3 -> 9 -> 8 -> 5 -> 15 -> 7 -> 2 -> 6 -> 18 = -1

On passe d'un nombre au suivant en faisant x -> (x*3) mod 19.
Le 9ème fait -1 donc c'est gagné.
Si c'est périodique sans passer par 1 bah tu peux quand même déterminer quel sera le 114eme reste sans trop de problème.

merci beaucoup, mais comment aurais-tu fais si c'était au millionième nombre que tu tombais sur de la congruence modulo 1. De plus, cette méthode est très manuelle.

Pour ce qui est de la périodicité, peux-tu éclairer ton propos, sachant que si tu as un nombre périodique, qui n'admet pas 1 comme chiffre de période mais avec une grosse puissance bah tu auras un reste a^grosse puissance, souvent plus grosse que ton modulo n, ce qui n'est pas très utile. En effet savoir que ton reste c'est 3^114 ne t'avance pas beaucoup

Le 02 octobre 2018 à 19:28:36 IntellectSup a écrit :
merci beaucoup, mais comment aurais-tu fais si c'était au millionième nombre que tu tombais sur de la congruence modulo 1. De plus, cette méthode est très manuelle.

Pour ce qui est de la périodicité, peux-tu éclairer ton propos, sachant que si tu as un nombre périodique, qui n'admet pas 1 comme chiffre de période mais avec une grosse puissance bah tu auras un reste a^grosse puissance, souvent plus grosse que ton modulo n, ce qui n'est pas très utile. En effet savoir que ton reste c'est 3^114 ne t'avance pas beaucoup

Pour comprendre tout ça plus en détail il faut faire appel à de la théorie des groupes.
Une première chose qu'on peut montrer, c'est que si n est premier, la première puissance k telle que a^k = 1 mod n est un diviseur de n-1
En particulier, a^(n-1) = 1 mod n, c'est le petit théorème de Fermat.
Ici, les seules possibilités étaient donc 2, 9 ou 18.

Si n n'est pas premier, les choses sont un poil plus compliquées. Pour que ça ait une chance de marcher, il faut déjà que a soit premier avec n (sinon on n'aura jamais a^k = 1 mod n, sauf pour k = 0, et la suite des a^k mod n sera périodique mais ne passera pas par 1).
Si a est premier avec n, on saura que a^phi(n) = 1 mod n, et que le plus petit k tel que a^k = 1 mod n sera un diviseur de phi(n), avec phi l'indicatrice d'Euler (https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler). C'est une généralisation du petit théorème de Fermat, puisque si n est premier, phi(n) = n-1.
En particulier, phi(n) < n donc de toutes manières tu sais que tu n'auras jamais à chercher plus loin que n.

Merci, ça devient tout de suite plus claire, même si ce sont des notions assez nouvelles pour moi