Comment résoudre le troisième trimestre de l'OMI de 1990

Aug 16 2020

Pour ma leçon sur commande, l'un des exercices que mon professeur m'a donné était la question 3 de l'article de l'OMI de 1990:

Trouver tous les entiers $n>1$ tel que $\frac{2^n+1}{n^2}$ est un entier.

Ma tentative:


Nous avons $$n^2|2^n+1\Rightarrow2^n+1\equiv0\pmod{n^2}\Rightarrow2^n\equiv-1\pmod{n^2}\Rightarrow2^{2n}\equiv1\pmod{n^2}$$ Soit $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$$d|n$, ou $\text{ord}_{n^2}(2)=2d$$d|n$ mais $2d\nmid n$.

Si $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, puis $n^2=1\Rightarrow n=1$. Cela contredit les exigences de$n$.

Si $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, puis $n^2=1$ ou $3$ alors $n$ est $1$ ou $\sqrt3$. Cela contredit également les exigences de$n$.

Si $\text{ord}_{n^2}(2)=d$ alors il existe un entier $k$ tel que $dm=n$. ensuite$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. Cela contredit$2^n\equiv-1$ que nous avons montré plus tôt.

Par conséquent $$\text{ord}_{n^2}(2)=2d$$

Par le théorème d'Euler $2^{\phi(n^2)}\equiv1\pmod{n^2}$, alors $2d|\phi(n^2)$. Comme$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$$k=\prod_{p|n}\frac{p-1}p$, et $n$ et $n^2$ partagent les mêmes facteurs premiers, nous avons $$\phi(n^2)=n^2\prod_{p|n}\frac{p-1}p=n\left(n\prod_{p|n}\frac{p-1}p\right)=n(nk)=n\phi(n)$$

Continuant,

$$2d|\phi(n^2)\Rightarrow2d|n\phi(n)\Rightarrow2|m\phi(n)$$

$dm=n$. Cela signifie soit$m$ est pair (ce qui implique $n$ est pair) ou $\phi(n)$ est même.


Malheureusement, je suis encore loin de résoudre le problème. Il est clair que montrer$n$ est pair ou $\phi(n)$ n'est même pas suffisant pour montrer que $\frac{2^n+1}{n^2}$ est un entier (les contre-exemples incluent $n=4$ et $n=5$). Il existe une infinité de nombres satisfaisant aux conditions que j'ai posées. Cependant, je ne sais pas trop comment procéder, alors j'aimerais avoir de l'aide pour terminer la question.

Réponses

Yesit'sme Aug 16 2020 at 11:34

$\textbf{Hint:}$Considérez le plus petit diviseur premier de $n$.

Utilisez ensuite le lemme "lever l'exposant".

Considérons à nouveau le deuxième plus petit nombre premier de $n$

Considérons d'abord le plus petit diviseur premier, disons $p$ de $n$.Ce ne peut pas être $2$. Ensuite,$2^{2n}=1 \pmod {p}$, mais aussi par FLT $2^{p-1}=1 \pmod {p}$.

Ces deux ensemble impliquent que $2^{gcd(p-1,2n)}=1 \pmod {p}$.Mais maintenant, $gcd(p-1,2n)=2$ depuis, tout autre prime de $n$ serait plus grand que $p-1$.Ceci implique que $3$ doit être le plus petit nombre premier de $n$ .depuis $2^2=1 \pmod{p}$ d'en haut.

Déduisez maintenant en utilisant cette levée du lemme de l'exposant que la puissance la plus élevée de $3$ partage $n$ est $1$.Puis, considérez le plus petit nombre $n/3$.

Utilisez un argument similaire à celui ci-dessus pour montrer qu'il doit être $7$.Mais du fait que $3 \mid n$ montrer que cela ne peut pas arriver, donc la seule solution serait $n=3$

(les détails sont omis depuis que je l'ai écrit pour lui servir d'indice)

Pour une solution détaillée .voir ici: aops