Problème d'arithmétique

Bonjour,

Je bloque sur ce problème d’arithmétique : Soit $k$ un entier strictement positif et $a_1,a_2,...,a_k$ des chiffres. Prouver qu’il existe un entier positif $n$ tel que les $2k$ derniers chiffres de $2^n$ sont, dans l’ordre suivant, $a_1,a_2,...,a_k,b_1,b_2,...,b_k$ pour certains chiffres $b_1,b_2,...,b_k$

Des idées pour résoudre ce problème ?

Merci !

Quand tu dis que les derniers chiffres sont dans cet ordre, c’est en lisant de droite à gauche ou de gauche à droite ? J’imagine que c’est de gauche à droite puisque sinon ça va pas marcher … mais on sait jamais.

Des idées pour résoudre ce problème ?

Deux pistes qui devrait aider à comprendre :

• commencer avec une écriture binaire ;
• faire quelques exemples avec $k=1,2$.

Merci de ta réponse Je ne comprend pas ta première proposition dès lors que le résultat est évidemment faux en binaire puisque $2^n$ s’écrit : $\underset {n\text{ fois}}{100...0}$

C’est pas parce que c’est faux que c’est inintéressant :-). Pourquoi en binaire ça marche pas alors qu’en décimal ça devrait marcher ? Qu’est-ce qui fait que ça marche pas ?

Ok Je vais tester avec plusieurs valeurs de $k$ et avec différentes bases pour voir un peu ce qui ne marche pas.

De gauche à droite ou de droite à gauche, les deux fonctionnent. Par contre j’imagine comme Holosmos que c’est de gauche à droite sinon les $b_i$ ne serviraient à rien.

Mais par contre, je vois pas trop en quoi ça peut aider de regarder sur des exemples ici. Enfin, je ne comprends pas trop tes conseils, Holosmos, j’ai l’impression que tu as en tête le problème des premiers chiffres (i.e. la version analyse plutôt qu’arithmétique).

De gauche à droite ou de droite à gauche, les deux fonctionnent.

Ah bah non ! Si tu prends $a_1=3$ tout à droite, ça va certainement pas marcher.

Mais par contre, je vois pas trop en quoi ça peut aider de regarder sur des exemples ici. Enfin, je ne comprends pas trop tes conseils, Holosmos, j’ai l’impression que tu as en tête le problème des premiers chiffres (i.e. la version analyse plutôt qu’arithmétique).

J’avais en tête qu’en passant par la description d’une récurrence sur l’apparition des chiffres, en plus d’un argument de cardinalité, on pourrait s’en sortir. Mais j’ai pas travaillé le détail, c’est juste une ébauche d’idée.

De toute façon faire des exemples ça n’a jamais été un handicap.

Bonsoir,

Le problème n’est pas si compliqué que cela, pour le résoudre il te suffit de manier rudimentairement les racines primitives et le LTE, et alors tu peux conclure par le théorèmes des restes chinois en exposant l’entier $n$ qui respecte les conditions de l’énoncé.

Si on prend $a_1 = 3$ tout à droite, on a $2^5 = 32$, ça donne $b_1 = 5$, il y a les $b$ qui comptent. D’après sa réponse, Thinking interprète de la même manière que moi. Par contre je ne comprends pas tes conseils. Il n’existe pas de racine primitive de l’unité modulo $10^n$ en général. C’est quoi le LTE ? Et pourquoi employer le théorème des restes chinois ?

Je conseille à Oubspa de commencer par formuler la situation avec des congruences, et de commencer par étudier plus généralement quels sont les derniers chiffres possibles de $2^n$.

Ah donc tu lis bien de gauche à droite. Parce que si tu mets le $b$ après le $a$ c’est de gauche à droite :-).

On montre que $2$ est une racine primitive modulo $5^k$ pour $ k \geq 1$, il s’ensuit : $o_{5^k}(2)$ est de la forme $4\cdot 5^l$ pour un entier $l$ avec $0\le l\le k-1$. De plus, par le LTE (Lifting The Exponent)

respecte la propriété de l’énoncé EDIT : si j’ai le temps j’écris la preuve complète

Aaah, oui, alors moi j’avais compris « de gauche à droite » ou « de droite à gauche » pour l’appellation « derniers chiffres ».

@Thinking : Ok, j’avais loupé l’étape qui était de montrer que $2$ est racine primitive.