C'est moi qui ai mal lu.
Ça fait toujours une proposition pour un autre problème.
Pour ta question je propose 1019, mais je crois qu'il serait bon de faire quelques simulations.
Mais la déduction n'est pas si évidente.
Si on prend, par exemple, a=15 on a cinq cycles que je définis par leur plus petit élément et leur longueur :
(1 ; 5) ; (3 ; 6) ; (5 ; 3) ; (7 ; 7) et (15 ; 2).
On regarde les entiers de 1 à 230 000.
Il y en a
61 335 qui arrivent dans le cycle de 1,
61 333 qui arrivent dans le cycle de 3,
30 667 qui arrivent dans le cycle de 5,
61 332 qui arrivent dans le cycle de 7,
15 333 qui arrivent dans le cycle de 15.
Les cycles (1 ; 5) ; (3 ; 6) et (7 ; 7) sont pratiquement équiprobables.
Il semble donc délicat de prédire les probabilités.
C'est plus simple que ça . On regarde dans l'OEIS la liste des nombres premiers a pour lesquels 2 est générateur de
3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, , ...
Pour tous ces entiers il n'y a que deux boucles a->2a->a et une autre nettement plus "grosse" passant par 1 et tous les entiers inférieurs à a . Les autres cas génèrent plusieurs boucles et diminuent fortement la taille de celle qui passe par 1 . La démonstration n'est pas complètement finalisée mais intuitivement c'est évident .
Imod
Intuitivement c'est évident je suis d'accord car mon intuition est la même.
Mais la démonstration n'est même pas esquissée.
Je viens de vérifier que parmi les entiers de 1 à 106 il y en a 981 qui ne passent pas par 1. Ce qui est le résultat que j'attendais, environ égal à 1/1019.
Mais ce n'est pas une démonstration.
Attention , mon intuition ne s'appuie pas sur une simulation ( je ne sais pas le faire ) .
Il y a toujours au moins deux boucles dont l'une est triviale ( de taille 2 dans et de taille 1 dans ) , les autres balayent exactement tous les entiers inférieurs à a ( modulo a ) . La justification est dans le fait que x->2x est une bijection de dans lui même .
Les 2 qui sont générateurs sont plutôt nombreux et c'est parmi eux qu'il faut chercher les solutions .
Mais bon , ce n'est pas complètement finalisé
Imod
Je n'ai pas fait de simulation : j'ai juste compté ( enfin fait compter par un petit programme ).
Une esquisse de démonstration.
Si a est un nombre premier « à deux boucles » cad que 2 est un générateur de alors pour arriver sur la boucle a->2a->a, il faut partir d'un multiple de a.
Et il est évident qu'en partant d'un multiple de a on reste toujours dans et que l'on arrive donc à cette boucle.
En fait la démonstration rigoureuse est relativement simple , pour a donné :
1°) Deux termes égaux modulo a finissent dans la même boucle .
2°) Chaque x modulo a appartient à une et une seule boucle .
3°) La boucle passant par 1 contient a-1 termes distincts ( modulo a ) si et seulement si a est premier et si 2 est un générateur de .
Imod
Quelles sont les conditions pour que 2 soit générateur?
Autrement dit, pourquoi 1009 n'est pas la solution?
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :