Puzzle reconstitué

Bonjour,
Quelqu'un pourrait-il me dire si le long raisonnement que je tiens ci-dessous est correct ?
Plus un raisonnement est long, plus le risque d'erreur est grand.
Merci d'avance.
Il s'agit pour moi de résoudre le problème suivant.

Trouver les entiers $n>0$ tels que $\dfrac{2^n+1}{n^2}$ soit entier.

Voici mon raisonnement.
$\fbox{1}$ [size=medium] $n$ impair et premières solutions. [/size]
On remarque immédiatement que, quel que soit $n$ (pair ou impair), l'entier $2^n+1$ sera impair.
De sorte que, si $n$ est pair, $n^2$ sera pair aussi et ne pourra diviser $2^n+1$, alors que, si $n$ est impair, $n^2$ sera impair aussi et pourra éventuellement diviser $2^n+1$.
Donc, on cherche $n$ obligatoirement impair.

Sachant $n$ impair, on ne peut pas s'empêcher de tester quelques petites valeurs impaires et on s'aperçoit de suite que $n=1$ et $n=3$ sont des solutions, la solution $n=1$ pouvant même être qualifiée de "triviale" puisque $1$ est "diviseur universel".
Mais on ne peut pas passer le reste de sa vie à tester toutes les valeurs impaires une par une. Il faut une méthode.

$\fbox{2}$ [size=medium] La méthode (résumée). [/size]
Puisque $n=3$ est une solution, les éventuelles autres solutions seront de la forme $n=3^mZ$, avec :
$m$, un entier naturel (éventuellement nul, ce qui ferait disparaître le facteur $3$),
$Z$, un entier strictement positif impair (éventuellement égal à $1$) et premier avec 3 (sinon, cela influencerait de façon incontrôlée la valeur de $m$).
La méthode consiste à déterminer $m$ et $Z$ autrement qu'au cas par cas. J'ajouterai même qu'il vaut mieux commencer par déterminer $m$. On verra pourquoi.

$\fbox{3}$ [size=medium] Détermination de $m$. [/size]
Si $(n)^2=(3^mZ)^2$ divise $2^{3^mZ}+1$, alors déjà $(3^m)^2=3^{2m}$ divise $2^{3^mZ}+1$.
Que dire de $m$ ?

$\fbox{3a}$ François Chaurien a proposé ailleurs une démonstration de ce que $3^{m+2}$ ne divise pas $2^{3^m}+1$. (Pour cette démonstration, voir mon message suivant.)
$\fbox{3b}$ : En élargissant le travail de François Chaurien, il est possible de démontrer que $3^{m+2}$ ne divise pas non plus $2^{3^mZ}+1$. (Pour cette démonstration, voir deux messages à moi plus bas.)
$\fbox{3c}$ : De ce dernier résultat, on déduit que toute puissance de $3$ égale ou supérieure à $3^{m+2}$ ne divise pas $2^{3^mZ}+1$.
[En effet, si $3^{m+2}=3^m\cdot 3^2$ ne divise pas $2^{3^mZ}+1$, alors il est évident que, pour tout entier $a$ strictement positif, $3^{(m+2)+a}=3^m\cdot 3^2 \cdot 3^a$ ne divisera pas $2^{3^mZ}+1$ non plus.]

De sorte que, si $2^{3^mZ}+1$ est divisible par $(3^m)^2=3^{\color{red}{2m}}$ mais pas par une puissance de $3$ égale ou supérieure à $3^{\color{red}{m+2}}$, alors du côté des exposants de $3$ on doit avoir $2m<m+2$, c'est-à-dire qu'on doit avoir $m<2$.
Puisque $m$ est un entier naturel, $m=0$ ou $m=1$.

$\fbox{4}$ [size=medium] Détermination de $Z$. [/size]
Rappel : $Z$ est un entier strictement positif impair et premier avec $3$.
Qu'en dire d'autre ?
Deux suppositions :

$\fbox{4a}$ $\underline{Z=1}$.
Si $Z=1$, alors le problème prend fin ici. En effet :
Si $Z=1$ et $m=0$, alors $(n)^2=(3^01)^2=(1)^2=1$ divise bien $2^{3^01}+1=3$ (solution déjà trouvée : $n=1$).
Si $Z=1$ et $m=1$, alors $(n)^2=(3^11)^2=(3)^2=9$ divise bien $2^{3^11}+1=9$ (solution déjà trouvée aussi : $n=3$).

$\fbox{4b}$ $\underline{Z>1}$.
Si $Z>1$, alors $Z\geq 5$ et sa décomposition en facteurs premiers compte un plus petit facteur premier $p$ (impair, forcément).
De sorte que si $(n)^2=(3^mZ)^2$ divise $2^{3^mZ}+1$, alors déjà $p$ divise $2^{3^mZ}+1$, ce qui en arithmétique modulaire donne, dans le respect de l'égalité $n=3^mZ$ :

$2^n+1\equiv 0\pmod{p}$
$2^n\equiv -1\pmod{p}$
$(2^n)^2\equiv (-1)^2\pmod{p}$
$2^{2n}\equiv 1\pmod{p}$ (Résultat 1)

Mais, étant donné que $p$ premier impair ne divise pas 2, le petit théorème de Fermat dit aussi :
$2^{p-1}\equiv 1\pmod{p}$ (Résultat 2)

De sorte que, combinant le résultat 1 et le résultat 2, on a (en vertu de la démonstration disponible trois messages à moi plus bas) :
$2^{PGCD(2n, p-1)}\equiv 1 \pmod{p}$.

Or, d'une part, on a $\underline{2n}=2\cdot (3^mZ)=\underline{2\cdot Z}$ si $m=0$, et $2n=2\cdot (3^mZ)=\underline{2\cdot 3\cdot Z}$ si $m=1$.
D'autre part, puisque $p$ est le plus petit facteur premier (impair) de $Z$ (impair), il suit que $p-1$ :
- est forcément premier avec $Z$,
- est pair, donc possède le facteur premier $2$,
- possède éventuellement le facteur premier $3$.

De sorte que :
si $2n=2\cdot Z$, alors $PGCD(2n, p-1)=2$.
si $2n=2\cdot 3 \cdot Z$, alors $PGCD(2n, p-1)=2$ ou $6$.

...résultats qui permettent de reprendre là où l'on s'était arrêtés, c'est-à-dire à $2^{PGCD(2n, p-1)}\equiv 1 \pmod{p}$, en envisageant les deux cas :
$\underline{\text{Si PGCD(2n, p-1)=2}}$, alors,
$2^2\equiv 1\pmod{p}$
$4-1\equiv 0\pmod{p}$
$3\equiv 0 \pmod{p}$
ce qui, en arithmétique modulaire, signifie que $p$ (premier impair) divise $3$. Donc, $p=3$.
Mais cette solution est inacceptable puisque $Z$, premier avec $3$, ne peut posséder de facteur premier égal à $3$. Hypothèse à rejeter.

$\underline{\text{Si PGCD(2n, p-1)=6}}$, alors,
$2^6\equiv 1\pmod{p}$
$64-1\equiv 0\pmod{p}$
$63\equiv 0 \pmod{p}$
Ici, $p$ premier impair, premier avec $3$, divise $63$. Donc, $p=7$.
Mais cette solution est inacceptable également. En effet, on calcule facilement que $3$ est l'ordre multiplicatif de $2$ modulo $7$. De sorte que, pour tout entier naturel $t$ :
$2^{1+3t}\equiv 2\pmod{7}$
$2^{2+3t}\equiv 4\pmod{7}$
$2^{3+3t}\equiv 1\pmod{7}$
Par conséquent, pour tout entier naturel $n$, $2^n+1$ ne peut être congru modulo $7$ qu'à $3$, $5$ ou $2$. Jamais à zéro. Donc $7$ ne divise jamais $2^n+1$.

L'hypothèse $Z>1$ ne conduisant qu'à des solutions à rejeter ($p=3$ et $p=7$), elle est elle-même à rejeter, ce qui renvoie à l'hypothèse $Z=1$ et aux deux seules solutions trouvées dans ce cadre-là, à savoir $n=1$ et $n=3$.

Réponses

  • Démonstration proposée par François Chaurien de ce que, pour tout $m \in \mathbb{N}$, $2^{3^m}+1$ est divisible par $3^{m+1}$ mais non par $3^{m+2}$.
    (En modifiant la mise en forme initiale, j'espère ne pas avoir dénaturé le raisonnement par récurrence de François Chaurien) :

    Supposons que, pour un $m \in \mathbb{N}$, l'entier $2^{3^m}+1$ soit divisible par $3^{m+1}$ mais pas par $3^{m+2}$.
    Alors, qu'en sera-t-il de l'entier $2^{3^{(m+1)}}+1$ ? Sera-t-il divisible par $3^{(m+1)+1}$, c'est-à-dire $3^{m+2}$, mais pas par $3^{(m+1)+2}$, c'est-à-dire $3^{m+3}$ ?
    La réponse est oui. En effet :

    Si $2^{3^m}+1$ est bien tel qu'il est supposé, alors il est de la forme $3^{m+1}q$, avec $q$ entier non multiple de $3$. Il vient :
    $2^{3^m}+1=3^{m+1}q$
    $2^{3^m}=3^{m+1}q-1$
    $2^{3^{m+1}}=(2^{3^m})^3=(3^{m+1}q+(-1))^3$
    $2^{3^{m+1}}=(3^{m+1}q)^3+3(3^{m+1}q)^2(-1)+3(3^{m+1}q)(-1)^2+(-1)^3$
    $2^{3^{m+1}}=3^{3(m+1)}q^3-3\cdot3^{2(m+1)}q^2+3\cdot3^{m+1}q-1$
    $2^{3^{m+1}}+1=3^{3m+3}q^3-3\cdot3^{2m+2}q^2+3\cdot3^{m+1}q$
    $2^{3^{m+1}}+1=3^{3m+3}q^3-3^{2m+3}q^2+3^{m+2}q$
    et en mettant le dernier terme en évidence :
    $2^{3^{m+1}}+1=(3^{m+2}q) \underbrace{(3^{2m+1}q^2-3^{m+1}q+1)}_{q'}$
    où $q'$ n'est pas plus un multiple de $3$ (à cause du terme $1$) que $q$ ne l'est.
    Cette dernière égalité montre bien que $2^{3^{(m+1)}}+1$ est divisible par $3^{m+2}$, mais pas par $3^{m+3}$ puisque ni $q$ ni $q'$ ne contiennent le facteur $3$).

    Or, déjà pour $m=0$, $2^{3^m}+1$ est divisible par $3^{m+1}$ mais pas par $3^{m+2}$. Donc, $2^{3^m}+1$ possède cette propriété pour tout $m \in \mathbb{N}$.
  • Démonstration de ce que $3^{m+2}$ ne divise pas non plus $3^{3^mZ}+1$

    Rappel :
    $Z$ est un entier strictement positif impair et premier avec $3$.
    Ajoutons que dans ce raisonnement on supposera $Z>1$, sinon $2^{3^m1}+1=2^{3^m}+1$ et il n'y a rien à démontrer de plus que ce qui a déjà été démontré au message précédent.
    En d'autres mots, ici, on a $Z\geq 5$.
    Puisqu'on a vu que $2^{3^{m}}+1$ est divisible par $3^{m+1}$ mais pas par $3^{m+2}$ pour tout $m \in \mathbb{N}$, posons encore une fois $2^{3^m}+1=3^{m+1}q$, avec $q$ non multiple de $3$. Il vient :

    $2^{3^m}=3^{m+1}q-1$
    $2^{(3^mZ)}=(2^{3^m})^Z= (3^{m+1}q+(-1))^Z$
    $2^{(3^mZ)}=\overset{Z}{\underset{j=0}{\Sigma}}(3^{m+1}q)^{Z-j}(-1)^j$
    Si on veut faire apparaître plus clairement (en bleu) les deux derniers termes de cette somme algébrique, cela donne :
    $2^{(3^mZ)}=\overset{Z-2}{\underset{j=0}{\Sigma}}(3^{m+1}q)^{Z-j}(-1)^j\color{blue}{+\binom{Z}{Z-1}(3^{m+1}q)^1(-1)^{Z-1}+\binom{Z}{Z}(3^{m+1}q)^0(-1)^Z}$
    où les coefficients binomiaux $\binom{Z}{Z-1}$ et $\binom{Z}{Z}$ valent respectivement $Z$ et $1$, d'où :
    $2^{(3^mZ)}=\overset{Z-2}{\underset{j=0}{\Sigma}}(3^{m+1}q)^{Z-j}(-1)^j\color{blue}{+Z(3^{m+1}q)-1}$
    où chaque terme, sauf les deux derniers (en bleu), compte une puissance de $3$ strictement supérieure à $3^{m+1}$ et une puissance de $q$ strictement supérieure à $q$. D'où, en faisant passer $\color{blue}{-1}$ de droite à gauche de l'égalité et en mettant $3^{m+1}q$ en évidence :

    $2^{(3^mZ)}+1=(3^{m+1}q)\times$$\underbrace{\text{((une somme algébrique de multiples de $3$) $+Z$}}_{q''})$
    où, étant donné que $Z$ est premier avec $3$, il vient que $q''$ n'est pas plus un multiple de $3$ que $q$ ne l'est. De sorte que cette dernière égalité montre bien que $2^{3^mZ}+1$ est divisible par $3^{m+1}$ mais pas par $3^{m+2}$.
  • D'une façon générale, si $p$ est un nombre premier qui ne divise pas $a$, on peut dire d'après la théorie (Gauss, Recherches arithmétiques, n$^\circ$45 et suivants) :
    1) qu'il existe un plus petit entier strictement positif $t$ tel que $a^t\equiv 1\pmod{p}$.
    2) que, pour tout entier naturel $m$, on aura $a^{mt}\equiv 1\pmod{p}$ (n$^\circ$46).
    3) que, pour un entier strictement positif $k$, si $a^k\equiv 1\pmod{p}$, on aura $k\equiv 0\pmod{t}$, c'est-à-dire que $k$ sera un multiple de $t$ (n$^\circ$48).

    Dans le problème qui nous occupe, puisque l'on arrive à $2^{2n}\equiv 1 \pmod{p}$ et $2^{p-1}\equiv 1 \pmod{p}$, il suit que $2n$ et $p-1$ sont tous les deux des multiples de $t$, tel que défini ci-dessus. Posons alors : $2n=\alpha t$ ainsi que $p-1=\beta t$ (avec $\alpha$, $\beta$ entiers strictement positifs).

    Maintenant :

    1) Si $\alpha$ et $\beta$ sont premiers entre eux :
    Alors PGCD$(2n, p-1)=$ PGCD$(\alpha t, \beta t)=t$.
    Et l'on a bien $2^{PGCD(2n, p-1)}=2^t\equiv 1\pmod{p}$, comme au point 1, ci-dessus.

    2) Si $\alpha$ et $\beta$ ne sont pas premiers entre eux :
    Alors PGCD$(\alpha, \beta)=\delta$ (avec $\delta$, entier strictement supérieur à $1$).
    Ce qui entraîne $\alpha=\delta \alpha'$ et $\beta=\delta \beta'$ (avec $\alpha'$ et $\beta'$ premiers entre eux).
    De sorte que PGCD$(2n, p-1)=$ PGCD$(\alpha t, \beta t)=$ PGCD$(\delta \alpha' t, \delta \beta' t)=\delta t$.
    Et l'on a bien $2^{PGCD(2n, p-1)}=2^{\delta t}\equiv 1\pmod{p}$, comme au point 2, ci-dessus.
  • Je n'ai pas regardé dans le détail, mais ça a bonne allure. Il s'agit d''un problème d'olympiade internationale, et à l'époque je l'avais cherché et j'avais trouvé une solution longue comme ça, et avec les mêmes ingrédients.
    Je vais voir ça de plus près tantôt. Après on regardera les solutions proposées dans la littérature.
    Bonne journée.
    Fr. Ch.
  • Ce problème est apparu dans l'OMI 1990, Problème-3.
  • Je ne voulais pas donner l'année pour qu'on ne se précipite pas sur les corrigés disponibles
  • E. Cidrolin vous présente toutes ses confuses.
  • Bof, tant pis, moi je ne sais jamais quand il est temps de corriger et je me fais gronder.
    Bien amicalement.
    Fr. Ch.
  • Vous voyez un problème de mathématiques et vous pouvez dire où et quand il a été posé ?

    Comme ces champions et championnes d'Echecs qui, voyant une position sur un échiquier, peuvent dire où et quand elle a déjà été jouée :
    - "Manille, Championnat du monde 1975, 28ème partie."

    C'est impressionnant !
  • @ Sneg

    Je ne puis répondre pour Cidrolin, et en ce qui me concerne, je ne vois pas toujours l'origine d'un problème, mais il y en a certains qui sont pour
    ainsi dire classiques, et il faut considérer que je suis un vieux monsieur qui en a vu beaucoup passer. À diverses époques je me suis occupé de compétitions mathématiques et de leur préparation, et je faisais attention aux énoncés qui paraissaient. Pour celui-ci, de 1990, c'était avant l'usage généralisé d'Internet, et il était déjà difficile de connaître les énoncés des Olympiades internationales car il régnait une certaine rétention d'information, mais je m'étais débrouillé pour les obtenir, j'ai déjà expliqué comment, par une filière luxembourgeoise ;-).

    J'avais cherché ce problème et j'avais noté une certaine parenté avec des problèmes d'un excellent livre que tu connais peut-être, et sinon, que je te conseille : W. Sierpinski, 250 problèmes de théorie élémentaire des nombres, Hachette Université 1972. La version anglaise : 250 Problems in Elementary Number Theory, Elsevier, 1970, est peut-être plus facile à trouver. Par exemple :
    $ \bullet$ Montrer qu'il existe une infinité d'entiers positifs $n$ tels que $n$ divise $2^n+1$ et déterminer tous ceux d'entre eux qui sont premiers.
    $ \bullet$ Montrer qu'il n'existe pas d'entier $n>1$ tel que $n$ divise $2^n-1$.

    C'est le bon usage des corrigés : ils peuvent servir à chercher des problèmes qui ressemblent. J'avais ainsi trouvé une solution pour celui-ci, je l'avais rédigée, et j'ai conservé ma rédaction. Ma solution utilise la notion d'ordre multiplicatif d'un entier $x$ modulo $m$, lorsque $x$ est premier avec $m$, qui est en fait l'ordre de la classe de $x$ dans le groupe multiplicatif des unités $(\mathbb Z/ m \mathbb Z)^{\times}$. Ici ce qui intervient, c'est l'ordre de $2$ modulo $3^q$.

    Bonne journée.
    Fr. Ch.
    05/01/2021
  • @Sneg
    Un gros meuble à tiroirs encombré de bilans,
    De vers, de billets doux, de procès, de romances,
    Avec de lourds cheveux roulés dans des quittances,
    Cache moins de secrets que mon triste cerveau.
  • Où trouver des solutions de ce problème 3 de l'OIM 1990 ?

    Un fil récent concernait un autre énoncé d'arithmétique, de l'OIM 1989 : http://www.les-mathematiques.net/phorum/read.php?5,2155480,2155786#msg-2155786. On y a parlé du site AOPS (Art Of Problem-Solving) qui donne les énoncés et des solutions des problèmes des OIM, mais je n'y ai pas trouvé la solution de ce problème 3 de 1990.
    Une solution figure ici : https://prase.cz/kalva/imo/isoln/isoln903.html
    J'ai trouvé aussi : https://math.stackexchange.com/questions/203976/find-all-n1-such-that-dfrac2n1n2-is-an-integer, qui ne signale pas que c'est un problème d'OIM.

    Solutions aussi dans les trois livres que j'ai cités dans l'autre fil :
    - Jean-Pierre Boudine, François Lo Jacomo, Roger Cuculière, Olympiades Internationales de Mathématiques de 1988 à 1998, Éditions du Choix, 1998.
    - Paul Bourgade, Olympiades internationales de mathématiques 1976-2005, Cassini, 2005.
    - Istvan Reiman, International Mathematical Olympiad 1959 - 1999, Anthem Press 2001.
    Il existe aussi un gros livre : Dusan Djukic & alii, The IMO Compendium (...) 1959-2004, Springer 2006, qui donne de nombreux énoncés posés mais aussi ceux qui étaient proposés et n'ont pas été retenus, et quelques solutions, mais pas de solution du problème 3 de 1990.

    A bisto de nas, ces solutions tournent autour des mêmes arguments, avec toutefois quelques différences.
    J'ai donc ici cinq solutions, plus la mienne et celle de Sneg. Il faudrait faire une étude comparative mais j'ai un peu la flemme.

    Bonne soirée.
    Fr. Ch.
  • Et bravo à Cidrolin pour sa citation.
    Mais si, la poésie est une solution.
  • Oui, Cidrolin. J’adore la poésie moi aussi.

    Un grand merci, Chaurien, pour toutes ces références et pour toutes tes remarques autour.
    C’est très gentil de ta part et très instructif !

    (Cela dit, question démonstrations, je crois que je bats le record de longueur.)

    Encore mille mercis et à bientôt, j’espère.
  • Juste une question :
    Les Olympiades Internationales de Mathématiques, c’est d’un haut niveau ?
  • Cela vole plus haut que l'aigle ne plane.
  • @ Sneg, au sujet des Olympiades internationales de mathématiques.
    Chaque pays participant envoie six jeunes dûment sélectionnés, élèves de l'enseignement secondaire. En 2020, il y avait 105 pays.
    Tu peux trouver les énoncés ici, pour juger par toi-même de la difficulté : https://www.imo-official.org/problems.aspx. Au fil des années, les problèmes sont de plus en plus difficiles : là au moins, le niveau monte ;-).
    Bonne soirée.
    Fr. Ch.
  • À nouveau, grand merci Chaurien pour tous ces renseignements et ce lien !
Connectez-vous ou Inscrivez-vous pour répondre.