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.

C'est aussi ma réponse

Elle se déduit des développements précédents .

Imod

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 à 10⁶ 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

On est sûr que a doive être premier ? Pour moi c'est une condition suffisante mais pas nécessaire.

Oui , si a n'est pas premier le cardinal de est strictement inférieur à a-1.

Imod

Quelles sont les conditions pour que 2 soit générateur?
Autrement dit, pourquoi 1009 n'est pas la solution?

Je ne pense pas qu'il y ait des critères connus . On sait que le groupe multiplicatif est cyclique dès que a est premier mais avec quels générateurs ? Pour répondre J'ai bêtement pioché dans l'OEIS .

Imod