Congruence proposée par Knuth

[koechlin]

Bonjour !
Je fais un TIPE sur le hasard. Je me suis donc penché sur la création de l'aléatoire par les générateurs à congruence linéaire, et j'essaie de démontrer certains des critères de Knuth.
Je suis presque parvenu à tout redémontrer en suivant la démonstration de Knuth, mais je ne parviens pas à prouver une relation qu'il laisse (parmi tant d'autres !) en exercice :
Soit un entier tel que . Montrer que si on se donne un entier tel que , alors (il s'agit bien de a exposant (2 exposant (e-1))
Auriez-vous des idées ? Il faut d'après Knuth utiliser un lemme démontré auparavant dans le livre, qui est :

Soit un nombre premier. Soit , tel que . On suppose que et que . Alors :
et

Je pense qu'il faut appliquer ce lemme plusieurs fois (quelque chose comme fois, ou ). J'avais notamment voulu appliquer le lemme à qui vérifie les conditions de départ du lemme avec et , mais le problème est que 2 ne rentre justement pas dans le cadre d'utilisation de ce lemme, puisque

Merci d'avance, si vous avez la moindre petite idée de la façon de me sortir de cette impasse (et si c'est très facile, vous pouvez toujours essayer de démontrer le lemme de Knuth :we: , bien que j'aie compris sa démonstration).

[Matt_01]

On peut écrire que
alors
Mais est pair. Donc
et donc
Mais
Ainsi, par récurrence on peut écrire :

Donc ce qui démontre le resultat.

[koechlin]

Merci beaucoup, c'est très astucieux !

Comme quoi, il n'était en fait pas nécessaire d'utiliser le lemme que Knuth avait démontré auparavant.

Encore merci !