Petit exercice de divisibilité
dans Arithmétique
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.
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.
Réponses
-
$\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) -
On trouve $u_n \equiv 2 \times 5^{2n} + (-1)^{n+1} 5^n-1 \, [9]$, il reste encore un peu de boulot.
-
Uvdose:
La décomposition $4=9-5$ n'est pas la bonne. $4=10-6$ semble plus adapter, j'y travaille. -
Alors, autant écrire $4=3+1$. Le binôme de Newton permet de déduire que $4^n\equiv3n+1\,(\text{mod}\;9)$.
-
Par récurrence...
-
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)$ -
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$. -
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. -
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). -
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. -
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. -
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 -
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. -
$(3+1)^n-1=-1+\sum_{k=0}^n 3^k$
-
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 -
Oui c'est clair, c'est une des méthodes que j'avais proposée dans mon message initial.
-
ou encore : $u_n=\left(4^n-1 \right) \left(2 \times 4^n + 1 \right)$ et les deux facteurs sont clairement divisibles par $3$.
-
GaBuZoMeu:
J'ai écrit un peu vite. Cela dit, cela ne change rien sur le fond ce qui est formidable.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres