21 divise ces nombres

YvesM · June 2016

Bonjour,

Je n'arrive pas à montrer que, pour tout entier non nul $n$, $21$ divise le nombre $\displaystyle N(n) = 1+2^{2^n} + 2^{2^{n+1}}.$

Une indication ?

J'ai calculé $\displaystyle N(1) = 21, N(2) = 273 = 13 \times 21, N(3) = 65 \ 793 = 3 \ 133 \times 21$ puis j'ai essayé par récurrence et encore de calculer le rapport $\displaystyle {N(n+1) \over N(n)}$... mais je bloque très rapidement.

Fin de partie · June 2016

Une idée qui me vient comme ça (j'ignore si elle a un quelconque intérêt).

Considérer le polynôme $P(x)=1+x+x^2$ puisque, sauf erreur, $N(n)=P\left(2^{2^n}\right)$ et résoudre le système de congruences:

$P(x)\equiv 0 \mod{3}$
$P(x)\equiv 0 \mod{7}$

Fin de partie · June 2016

$(1+x+x^2)(1-x)=1-x^3$

Nous savons que $x^3\equiv x\mod{3}$ d'après le petit théorème de Fermat.

Donc:
$(1+x+x^2)(1-x)\equiv 1-x \mod{3}$

Si, en outre, $P(x)\equiv 0 \mod{3}$ alors on doit avoir $x\equiv 1\mod{3}$
Or,
$P(1)=3$
donc les solutions de $P(x)\equiv 0 \mod{3}$ sont les entiers $x=3k+1$ avec $k$ entier quelconque.

En espérant ne pas avoir écrit d'énormités.

PS:
Ce qui est au dessus est peut-être inutile.

Les nombres $X_n=2^{2^n}$ sont congrus à $1$ modulo $3$
En effet,
$X_{n+1}=X_n^2$ et $X_1=4=3\times 1+1$.

PS2:
Il reste à régler le cas pour $7$ :-D

Cidrolin · June 2016

Waclaw Sierpinski en a fait le problème 123 page 66 de son "250pbs in elementary number theory"

YvesM · June 2016

Bonjour @Cidrolin,

Ai-je une chance de trouver en cherchant encore et en bricolant, ou la résolution de ce problème est-elle ardue ?

Cidrolin · June 2016

Ce n'est pas très difficile.

Fin de partie · June 2016

On montre (en faisant 7 calculs) que les seules valeurs, modulo $7$, qui annulent $P$ sont $2$ et $4$

et $2^2=4$ et $4^2=2\times 7+2$

On se rappellera que $2^{2^{n+1}}=\left(2^{2^n}\right)^2$

jacquot · June 2016

Bonsoir Yves,

Plutôt que de calculer le quotient $\dfrac {N(n+1)}{N(n)}$, tu pourrais t'intéresser
à la différence $N(n+1)-N(n)$

J'obtiens, sauf erreur $2^{2^n}D(n)$ avec $D(n)=2^{3\times 2^n}-1$

Et là, on peut faire une deuxième récurrence.$D(n+1)-D(n)=2^{3\times 2^n}(2^6-1)$

Je n'ai pas suivi la piste proposée par Fin de partie, qui me semble plus élégante si elle aboutit.

Amicalement. jacquot
[Edit : J'ai corrigé la définition de mon $D(n)$, pardon. ]

claude quitté · June 2016

$2^2 = 4$, $4^2 = 16$, $16^2 = (-5)^2 = 4$.

Fin de partie · June 2016

Je résume la démarche.

On considère le polynôme $P(x)=1+x+x^2$

On montre aisément que:

$1)P(x)\equiv 0\mod{3}$ si et seulement si $x\equiv 1\mod{3}$
$2)P(x)\equiv 0\mod{7}$ si et seulement si $x\equiv 2\mod{7}$ ou $x\equiv 4\mod{7}$

On peut montrer par récurrence (sachant que $2^{2^{n+1}}=\left(2^{2^{n}}\right)^2$ et $4^2=7\times 2+2$, $2^2=4$)

Que:
Pour tout $n>0$ entier on a:

3) $2^{2^{n}}$ est congru à $1$ modulo $3$
4) $2^{2^{n}}$ est congru à $2$ modulo $7$ ou est congru à $4$ modulo $7$

PS:
$N(n)=P \left(2^{2^{n}}\right)$

YvesM · June 2016

Bonjour,

J'ai trouvé par récurrence en suivant l'approche élémentaire (donc de mon niveau) de @jacquot.

Soit, pour tout entier non nul $n$, $\displaystyle N(n) = 1+ 2^{2^n} + 2^{2^{n+1}}.$

On forme la différence $\displaystyle N(n+1)-N(n) = 2^{2^{n+2}}-2^{2^n} = 2^{2^n} (2^{3.2^n}-1)$ ; on pose $\displaystyle M(n) = 2^{3.2^n}-1$ et on établit par récurrence que $\displaystyle 21\mid M(n)$ ainsi :
- pour $\displaystyle n=1$, on calcule $\displaystyle M(1) = 2^6-1 = 63 = 3 \times 21$
- pour $n$ quelconque, on suppose que $\displaystyle 21\mid M(n)$, et alors $\displaystyle M(n+1) = 2^{3.2^{n+1}}-1 = (2^{3.2^n})^2-1 = (M(n)+1)^2-1 = M(n)(M(n)+2)$ qui est bien divisé, comme $M(n)$, par $21$.

On peut donc écrire $\displaystyle N(n+1) = N(n) + 2^{2^n} M(n)$ avec $\displaystyle 21\mid M(n).$
Et on établit par récurrence que $\displaystyle 21\mid N(n)$ :
- pour $\displaystyle n=1$, on calcule $\displaystyle N(1) = 21$
- pour $n$ quelconque, on suppose que $\displaystyle 21\mid N(n)$, et alors $\displaystyle N(n+1)=N(n) + 2^{2^n} M(n)$ qui est bien divisé, comme $\displaystyle N(n)$ et $\displaystyle M(n)$, par $21$.

C'est l'écriture $\displaystyle 2^{2^{n+2}}-2^{2^n} = 2^{2^n} (2^{3.2^n}-1)$ que je ne voyais pas...

Merci.

claude quitté · June 2016

La suite en question, à partir de l'indice 1, est 2-périodique modulo 21 (cf mon précédent post).

jacquot · June 2016

(tu) claude quitté

Fin de partie · June 2016

Cela ne m'étonnerait pas que cet exercice figure dans un manuel de terminale S.
Cela pourrait faire un problème d'arithmétique accessible avec le bon choix de questions.

Cidrolin · June 2016

Ce qu'en dit Sierpinski : 53563

christophe c · June 2016

@CQ, pour les lecteurs qui tomberont sur le fil par google, un petit "modulo 21" ne serait peut-être pas de trop dans ton premier post :-D

claude quitté · June 2016

@cc Certes. Car on pourrait croire que je ne sais pas calculer (ce qui est le cas). Mais comme il y avait 21 dans le titre du fil, j'ai cru que personne n'irait penser que je faisais du calcul modulo $15$. Je me suis dit que j'allais ajouter $1 + 4 + 16 = 0$ et je ne sais plus pourquoi je l'ai pas écrit (C.Q. malicieux ?). Dans mon deuxième post, j'ai quand même mentionné ``$2$-périodique modulo 21''. Je dois avouer que c'est la première chose qui m'est venue à l'idée : faire du calcul modulo $21$. J'ai commencé à faire un petit tableau avec en première ligne $n = 1, 2, 3, 4, \cdots$, en deuxième ligne $2^{2^n}$ et en troisième ligne le carré de la deuxième. Je m'attendais à aller assez loin dans $n$ mais cela s'est stoppé tout de suite.

Je ne risque pas d'être poursuivi ?

blaise · June 2016

J'ai fait un peu différemment. Tout d'abord, $N(n)=1+2^{2^n}(1+2^{2^n})$. Si on considère la suite $u_n=2^{2^n}$, on montre par récurrence à partir de $u_1$, en utilisant la relation $u_{n+1}=u_n^2$, que $u_n = 1 \mod 3$ et $u_n = 2$ ou $4 \mod 7$ . On en déduit que $N(n)=1+u_n(1+u_n)$ est divisible par $3$ et $7$, et donc par $21$.

bisam · June 2016

Et si, bêtement, on remarquait que $N(n+1)$ est divisible par $N(n)$ et que $N(1)=21$, on conclurait aisément, non ?

Tout cela parce que (en reprenant les notations des posts précédents) $P(x^2)=1+x^2+x^4=(1+x+x^2)(1-x+x^2)=P(x)P(-x)$ et que $N(n)=P\left(2^{2^n}\right)$...

Fin de partie · June 2016

Des trucs bêtes comme ça je veux bien en avoir en tête tous les cinq minutes. :-D

Fin de partie · June 2016

La solution de Bisam rend encore plus accessible (on a encore le droit de rêver) ce problème à un élève de terminale S:

Une ébauche de présentation d'un exercice destiné à démontrer ce résultat:

1) On considère la fonction $P$ définie sur tout entier $m$ naturel par:
$P(m)=1+m+m^2$

a) Montrer que $P(m^2)=P(m)P(-m)$.

b) On considère la suite d'entiers $(u_n)$ définie pour tout $n$ entier naturel non nul par:

$u_n=P\left(2^{2^n}\right)$

Montrer que pour tout entier naturel non nul $n$, $u_{n}$ divise $u_{n+1}$

2) Montrer par récurrence que pour tout entier naturel non nul $n$, $21$ divise $u_n$.

21 divise ces nombres

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 11