Mathématiques - Exercice d'arithmétique

Exercice d'arithmétique
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: Tomy

Bonsoir, voilà un petit exo d'arithmétique pas facile je trouve:
"Trouver tous les entiers naturels non nuls tels que n² divise (2^n + 1)"

après quelques essais, il semble que ça marche pour n=1 et n=3. De plus, on doit avoir n impair (bon je sais ça nous avance pas des masses

), voila donc si vous avez quelques idées pour résoudre cet exo ou même pour réduire les conditions que l'on doit avoir, je serais ravi de les lire

Bonne soirée

Posted by: hans

Si a|b, a<=b.

Posted by: redwolf

Bonjour.
J'ai bien l'impression que 1 et 3 sont seuls dans cette catégorie, mais j'arrive juste à prouver ceci :
Le plus petit facteur premier de $n$ doit être 3 :

En effet, si on appelle $p$ ce facteur premier, et si $2^n\equiv -1 [n^2]$ , on a $2^{2n}\equiv 1 [p]$ .
L'ordre de 2 mod $p$ divise donc à la fois $2n$ et $p-1$ et il doit donc diviser leur pgcd.
$p-1$ n'est divisible par aucun des nombres premiers qui divisent n. Le pgcd de $p-1$ et $2n$ est donc 2.

Pour conclure : le seul nombre premier pour lequel l'ordre de 2 divise 2, c'est 3.

Posted by: redwolf

ReBonjour.

A moins que je ne passe à côté d'une évidence, l'exercice n'est vraiment pas facile.

J'ai montré que $n$ était (presque) sans facteur carré :
les nombres premiers $p$ tels que $2^d\equiv 1 [p^2]$ où $d$ est l'ordre de 2 modulo $p$ , sont extrêmement rares. On n'en connaît que deux : 1093 et 3511 mais personne ne sait démontrer qu'il n'y en a pas d'autre.
(sur ce sujet, voir http://mathworld.wolfram.com/WieferichPrime.html).

En revanche, pour tous les autres, on montre que l'ordre de 2 modulo $p^k$ est $d\times p^{k-1}$ . Je te laisse ceci en exercice.
A partir de là, si $n=p^k n'$ avec $(p,n')=1$ , $p^{2k}\mid 2^n+1$ . Donc $2^n\equiv -1[p^{2k}]$ et $2^{2n}\equiv 1[p^{2k}]$ . L'ordre de 2 modulo $p^{2k}$ divise donc $2n$ , c'est-à-dire que $d\times p^{2k-1}$ divise $2n$ . D'où $2k-1\leq k$ et $k\leq 1$ .

Un argument similaire à celui de mon précédent message montre que le deuxième plus petit nombre premier qui divise $n$ doit être 7 et le suivant est supérieur à 43 (en fait, c'est forcément 43, 127, 337 ou 5419).

Voilà... donc pour l'instant, $n$ est sans facteur carré (sauf peut-être pour 1093, 3511, et éventuellement quelques autres) et divisible par 21 (si $n\neq 3$ ).

Posted by: redwolf

Ca y est ! Et sans se casser autant la tête :

Dès qu'on a montré que le deuxième facteur premier doit être 7, c'est fini, parce qu'aucune puissance de 2 n'est congrue à -1 modulo 7.

Posted by: babulle

il y a peut-être une autre preuve. mais je suis un peu rouillée, et je ne suis pas certaine de mon raisonnement.
$n^2$ divise $2^n +1$
donc il existe un entier k tel que $kn^2=2^n +1$
donc $kn^2-1=2^n$
et $(\sqrt k n -1)(\sqrt k n+1)=2^n \qquad (1)$
on prouve par un raisonnement par l'absurde que $\sqrt k$ est un entier (sinon, il vient de (1) que n n'est pas entier non plus)
donc il existe p et q tels que $\sqrt k n -1$ divise $2^p$
et $\sqrt k n +1$ divise $2^q$
en notant $\gamma = \sqrt k n -1$
on a $\gamma$ divise $2^p$ et $\gamma+2$ divise $2^q$
donc $\gamma= 2$ et n est un entier tel qu'il existe k tel que $$n= \frac 3 {\sqrt k}$ donc n=1 ou n=3

Posted by: redwolf

Bonjour Babulle.

Peux-tu préciser ton raisonnement par l'absurde qui prouve que $\sqrt{k}$ est un entier ? Je ne vois vraiment pas.

Merci

Posted by: babulle

bon, alors, de mémoire, vu que j'ai laissé mes notes sur mon bureau:

supposons que $\sqrt k$ n'est pas entier.
on se souvient de la preuve que $\sqrt 2$ est irrationnel, le résultat est facilement généralisable et connu: si la racine d'un entier n'est pas entiere, elle n'est pas rationnelle non plus.
donc $\sqrt k$ est irrationnel.

selon (1), on a $\sqrt k n -1 = \frac{2^n}{\sqrt k n +1}$
donc $n =\frac1{\sqrt k} \left( \frac{2^n}{\sqrt k n +1} +1\right)$
et $n = \frac{2^n+\sqrt k n +1}{kn +\sqrt k } \times \frac{kn -\sqrt k}{kn -\sqrt k }$
d'où $n = \frac{2^nkn+\sqrt k (-2^n+kn^2-1)}{k^2n^2 - k }$
Or est est un entier, donc n s'écrit sous la forme $\alpha + \beta \sqrt k$ avec $\alpha$ et $\beta$ rationnels.
Donc n est irrationnel, ce qui est contradictoire.

Posted by: redwolf

Bonsoir.

Le problème dans la preuve précédente, c'est que le nombre $\beta$ dont le numérateur est égal à - $2^n+kn^2-1$ est nul par hypothèse ! Le terme en $\sqrt{k}$ disparait, et on ne peut rien en déduire sur $\sqrt{k}$ .

De toute façons, ce raisonnement n'utilisait pas la forme particulière de l'entier $2^n$ . S'il était valable, on aurait donc démontré :

Si $kn^2-1$ est un entier... alors $k$ est un carré ! Ce qui est évidemment faux.

Posted by: babulle

c'est juste, je n'avais pas fait attention. comme je l'ai dit précédemment, je suis un peu rouillée