Petit exercice de divisibilité

Gilles old · August 2017

Bonjour,

Je suis en train de chercher des méthode pour prouver que $u_n=2^{2n}\left(2^{2n+1}-1\right)-1$ est divisible par 9 pour tout entier naturel $n$.

En écrivant $u_n = 4^n\left(2\times 4^n-1\right)-1$, le résultat vient facilement car les restes de $4^n$ modulo 9 sont 1, 4 et $-2$.

La relation de récurrence $u_{n+1}=16u_n +3 (5+2^{2n+2})$ fonctionne également, après avoir prouvé que $5+2^{2n+2}$ est divisible par 3 pour tout $n$.

Avez-vous d'autres idées ?

Merci.

Gilles.

Fin de partie · August 2017

$\begin{align}u_n&=2\times 4^{2n}-4^n-1\\
&=2\times (9-5)^{2n}-(9-5)^n-1
\end{align}$

En développant avec la formule du binôme de Newton on obtient le reste par la division euclidienne par 9. (on a une expression en fonction de n qui est congrue à $u_n$ modulo 9)

Gilles old · August 2017

On trouve $u_n \equiv 2 \times 5^{2n} + (-1)^{n+1} 5^n-1 \, [9]$, il reste encore un peu de boulot.

uvdose · August 2017

@Fin de partie : autant écrire $4\equiv-5\,(\text{mod}\;9)$ et déduire que $u_n\equiv 2\times5^{2n}-(-5)^{n}-1\,(\text{mod}\;9)$. Mais bon, quelle est la plus-value de cette opération ?

Edit : je n'avais pas vu le message de Gilles au moment où j'ai posté le mien.

Fin de partie · August 2017

Uvdose:

La décomposition $4=9-5$ n'est pas la bonne. $4=10-6$ semble plus adapter, j'y travaille.

uvdose · August 2017

Alors, autant écrire $4=3+1$. Le binôme de Newton permet de déduire que $4^n\equiv3n+1\,(\text{mod}\;9)$.

Chaurien · August 2017

Par récurrence...

Chaurien · August 2017

Oups c'était déjà dans le premier message.
Moi je voyais : $u_n-u_{n-1}=15.2^{2n-1}(4^{n-1}-1)$

Fin de partie · August 2017

Ma décomposition de $4$ n'était pas la bonne.
Essayons plutôt $4=10-6$

Pour tout $m>1$ entier naturel non nul,

$\begin{align}4^m&=(10-6)^m\\
&=\sum_{k=0}^{m}\binom{m}{k}(-6)^k10^{m-k}\\
&=10^m-6m\times 10^{m-1}+\sum_{k=2}^{m}\binom{m}{k}(-6)^k10^{m-k}
\end{align}$

Pour tout $l$ entier naturel non nul,

$\begin{align} 10^l&=(9+1)^l\\
&=\sum_{j=0}^l \binom{l}{j} 9^j\\
&=1+ 9\sum_{j=1}^l \binom{l}{j} 9^{j-1}\\
\end{align}$

Pour tout $k>1$, $6^k=2^k3^k$ est divisible par $9$.

Ainsi, pour tout $m>1$ entier naturel non nul,
Il existe un entier $\text{R}(m)$ tel que,

$\displaystyle 4^m=1-6m+9\text{R}(m)$

Ainsi,

$\begin{align}u_n&=2\times 4^{2n}-4^n-1\\
&=2\left(1-6(2n)+9\text{R}(2n)\right)-(1-6n+9\text{R}(n))-1\\
&=9\Big(2\text{R}(2n)-\text{R}(n)-2n\Big)
\end{align}$

Donc $u_n$ est divisible par $9$ pour tout $n>1$.

uvdose · August 2017

1) @Fin de partie : autant écrire $4=3+1$ (c'est ce que je disais un peu plus haut).

2) Sinon, on peut faire comme ça :

On a $u_n=2^{4n+1}-2^{2n}-1$, donc $u_{n+3}=4096\times2^{4n+1}-64\times2^{2n}-1$. Comme $4096\equiv1\;(\text{mod}\;9)$ et $64\equiv1\;(\text{mod}\;9)$, on en déduit que $u_{n+3}\equiv u_n\;(\text{mod}\;9)$. La suite $(u_n)$ est donc $3-$périodique modulo $9$ ; comme $u_0=0$, $u_1=27$ et $u_2=495$ sont divisibles par $9$, c'est fini.

Gilles old · August 2017

Merci pour vos contributions, celle que j'aime particulièrement est celle de uvdose : $4^n\equiv3n+1\,(\text{mod}\;9)$. En plus je viens d'apprendre à générer à la volée les exercices du type : montrer que $3^n-2n-1$ est divisible par 4 pour tout $n$. (tu)

La méthode de la suite périodique est intéressante, je pense que je vais l'appliquer à d'autres exos.

(Je suis en train de préparer la fiche d'exos pour les TS spé maths).

uvdose · August 2017

Ou alors, on peut écrire : $u_n=64^n-4^n(4^n-1)^2-1$. On a $4\equiv1 \;(\text{mod}\;3)$ donc $4^n\equiv1 \;(\text{mod}\;3)$, ce qui entraîne que $(4^n-1)^2$ est divisible par $3^2=9$. Comme $64\equiv1 \;(\text{mod}\;9)$, on en déduit que $u_n\equiv 1-0-1\equiv 0\;(\text{mod}\;9)$.

Edit : on peut même écrire $u_n=(4^n-1)[2(4^n-1)+3]$ pour simplifier encore un peu.

Fin de partie · August 2017

Uvdose:
La décomposition $4=3+1$ conduit, en effet, à des calculs plus simples que les miens, en utilisant seulement la formule du binôme de Newton.

AP · August 2017

Une autre (peut être....) façon
$u_n=2X_n^2-X_n-1$ avec $X_n=4^n$
or modulo 9, $X_n$ ne prend que 3 valeurs $1,4,7$
et les trois valeurs correspondantes de $u_n$ sont
2-1-1=0 soit 0 mod 9
32-4-1=27 soit 0 mod 9
98-7-1=90 soit 0 mod 9

Fin de partie · August 2017

Uvdose:

Avec l'égalité que tu donnes,

$u_n=(4^n-1)[2(4^n-1)+3]$

En montrant que $4^n-1$ est divisible par $3$, on montre que $u_n$ est divisible par $9$ pour $n>0$.
(tu l'as fait par les congruences)

Sans congruence,

$\begin{align}4^n-1&=(3+1)^n-1\\
&=-1+\sum_{k=0}^n \binom{n}{k}3^k\\
&=\sum_{k=1}^n \binom{n}{k}3^k\\
&=3\sum_{k=0}^{n-1} \binom{n}{k+1}3^k\\
\end{align}$

Merci à GBZM pour sa vigilance.

GaBuZoMeu · August 2017

$(3+1)^n-1=-1+\sum_{k=0}^n 3^k$

Sûr de chez sûr ?

jean-éric · August 2017

Bonjour,

il suffit de regarder les cas $n=0, \ n=1$ et $n=2$, et de raisonner modulo 9 car $2^{2n}\equiv 1, \ 4, \ 7$ puis pour $n=3$ on retrouve 1. Et donc on a facilement que $u_n \equiv 0$ modulo 9.

Espérant avoir été clair.

Jean-éric