Une congruence intéressante — Les-mathematiques.net The most powerful custom community solution in the world

Une congruence intéressante

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

Réponses

  • 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.
  • 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$.
  • Quelle valeur de m choisis-tu dans les deux cas ?
  • 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é.
  • 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" :)
  • 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 :)
  • 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]
  • Puisque tu sembles aussi avoir la démo pour $n$ pair, je n'ai pas besoin de te donner ma solution B-)
  • 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
  • Ok. Je disais que c'était assez technique, pas forcément très technique ;)

  • 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...
  • 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 ?

  • 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é.
  • 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 :

  • Bravo. Un peu spécialiste en arithmétique ?
  • Spécialiste, pas vraiment, hélas. Mais intéressé, ça, sûrement :)
  • C'est vrai que l'arithmétique est magique.
    Et quelle est ta formation ?
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!