Une congruence intéressante

gai requin · July 2011

Montrer que pour tout entier naturel non nul n, il existe un entier naturel m tel que n divise 2^m+m.

blaaang · July 2011

Déjà, grâce au petit théorème de Fermat, on peut prouver facilement que c'est vrai pour $n$ de la forme $2^{\theta}p$ où $p$ est un entier premier impair.

blaaang · July 2011

On peut généraliser ce que j'ai dit ci-dessus aux entiers $n$ qui s'écrivent sous la forme $2^{\theta}s$ où $s$ est un entier impair tel que $\varphi(s) \wedge s=1$.

gai requin · July 2011

Quelle valeur de m choisis-tu dans les deux cas ?

blaaang · July 2011

Pour le deuxième cas (qui englobe le premier), tu choisis $k_0 \in \mathbb{N}$ tel que $1+k_{0} \varphi(s) \equiv 0 \; $ puis $k \in \mathbb{N}$ tel que $k_0+ks \equiv 0 \; [2^{\theta}]$. Tu peux alors vérifier que $m=(k_0+ks) \varphi(s)$ convient.

Je parviens également à prouver l'existence d'un $m$ pour un $n$ de la forme $p^{\theta}$ où $p$ est premier et $\theta > 1$. Je posterai quelques détails quand j'aurai plus de temps si tu es intéressé.

gai requin · July 2011

En fait, j'ai une solution assez technique qui marche pour tout $n$... mais je suis très intéressé par ton approche plus "théorème chinois"

blaaang · July 2011

Si $p$ est un nombre premier impair, on peut construire une suite d'entiers naturels $(m_k)_{k \geqslant 1}$ telle que $p^k \; | \; 2^{m_k}+m_k$ de la façon suivante : $m_1=p-1$ et $m_{k+1}=m_k+(p-1) \left( 2^{m_k}+m_k\right)$.

Si tu pouvais expliquer dans les grandes lignes les arguments que tu utilises pour traiter le cas général, je suis preneur

blaaang · July 2011

Bon, je pense pouvoir traiter entièrement le cas $n$ impair... Voici le plan de la démonstration :

Notons $E$ l'ensemble des entiers $n \geqslant 1$ tels qu'il existe $m \in \mathbb{N}$ avec $n \; | \; 2^m+m$.

Propriété : Soit $n$ un entier naturel impair. Alors $n \in E$ $\Leftrightarrow$ $n \wedge \varphi(n) \in E$.

Conséquence : Tout entier naturel impair appartient à $E$.

( utiliser la suite définie par $u_0=n$ et $u_{k+1}=u_k \wedge \varphi(u_k)$ )

[Je viens de voir ça rapidement mais je crois pouvoir traiter aussi le cas $n$ pair $-$ Je poste des détails dès que j'ai un peu de temps]

gai requin · July 2011

Puisque tu sembles aussi avoir la démo pour $n$ pair, je n'ai pas besoin de te donner ma solution B-)

blaaang · July 2011

J'aurais pourtant bien voulu voir cette solution très technique dont tu parles...
Dès que tu l'auras postée, je posterai la mienne :P

gai requin · July 2011

Ok. Je disais que c'était assez technique, pas forcément très technique

Sylvain · July 2011

Disons que ça reste dans le cadre de l'arithmétique élémentaire, sauf peut-être le passage sur l'ordre de 2 dans Z/NZ. Mais il faut reconnaître que ce n'est pas trivial...

blaaang · July 2011

Ta solution est courte. Comme promis, voici la mienne

Quelle est l'origine de cette question ? S'agit-il d'un exercice de type olympiades ?

gai requin · July 2011

Merci pour tes recherches.
Cet exercice m'a été donné par un ami qui séchait dessus et je ne sais pas où il l'avait pêché.

blaaang · July 2011

Je parviens à généraliser le résultat de la façon suivante :

Propriété : Soit $a$ un entier supérieur ou égal à $2$. Alors pour tout $n \in \N$, il existe $m \in \mathbb{N}$ tel que $n \; | \; a^m+m$.

Voir fichier ci-dessous pour les détails :