par Patrick » sam. 14 sept. 2013 21:15
Bonsoir,
Voici un problème sur le thème des suites associé à l’arithmétique.
Je pense avoir rédigé l'essentiel, même si je ne suis très sûr des démonstrations en 2c et 2d.
J'ai facilité la lecture un peu longue avec LaTex, Merci pour la vérification.
1) Déterminer le PGCD de \(4^2 - 1\) et de \(4^6 - 1\)
2) Soit \((u_n)\) la suite définie par :
\(\quad\forall n\in\mathbb{N}\quad u_{n+2}=5u_{n+1}-4u_n\) avec \(u_0=0\), \(u_1=1\)
- a. Calculer \(u_2\), \(u_3\) et \(u_4\),
- b. Démontrer que, \(\forall n\in\mathbb{N}\) : \(u_{n+1}=4u_n+1\),
- c. Démontrer que, \(\forall n\in\mathbb{N}\), \(u_n\) est un entier naturel,
- d. En déduire, \(\forall n\in\mathbb{N}\), le PGCD de\(u_n\) et de \(u_{n+1}\).
3) Soit \((v_n)\) la suite définie par : \(\forall n\in\mathbb{N},\quad v_n = u_n+\frac{1}{3}\)
- a. Démontrer que \((v_n)\) est une suite géométrique,
- b. \(\forall n\in\mathbb{N}\), exprimer \(v_n\), puis \(u_n\), en fonction de \(n\),
- c. Déterminer, \(\forall n\in\mathbb{N}\), le PGCD de \(4^n- 1\) et de \(4^{n+1}-1\).
_____________________________________________________
1) Rappels utiles : \(a^3-b^3=(a-b)(a^2+ab+b^2)\) et \(a|b\quad\Longleftrightarrow\quad pgcd(a,b)=a\).
Compte tenu des rappels, on peux répondre à la question : \(4^6-1=(4^2)^3-1=(4^2-1)[(4^2)^2+1\times 4^2+1]\quad\Longleftrightarrow\quad pgcd(4^2 - 1,\ 4^6 - 1)=4^2 - 1\).
2) a. Les premiers termes de \((u_n)\) sont :
\(u_0=0,\ u_1=1,\ u_2=5,\ u_3=21,\ u_4=85\).
\(\quad\)b. Démonstration par récurrence :
Initialisation Ok, car \(u_1=4\times u_0+1=4\times 0+1=1\),
Récurrence : on suppose \(u_{n+1}=4u_n+1\quad\Longleftrightarrow\quad u_{n+1}-1=4u_{n}\) vrai.
Donc par substitution : \(u_{n+2}=5u_{n+1}-(u_{n+1}-1)=4u_{n+1}+1\)
Conclusion : la preuve est faite, car \(u_{n+2}=4u_{n+1}+1\) est le rang \(n+1\) de \(u_{n+1}=4u_n+1\).
\(\quad\)c. On sait que \(u_0=0\) est un entier naturel et je suppose que \(u_n=4u_{n-1}+1\) aussi, alors \(4\times u_n\) est un entier, de même que \(u_{n+1}=4u_{n}+1\) CQFD ?
\(\quad\)d. Maintenant que l'on sait qu'il existe des entiers \(u_{n+1}\) et \(u_n\), grâce au théorème de BEZOUT, on peut affirmer que le \(pgcd(u_{n+1},u_n)=1\), puisque \(u_{n+1}-4u_{n}=1\) et les coefficients \(1\) et \(-4\) sont premiers entre eux. CQFD ?
3) a Concernant la relation entre les suites \((u_n)\text{ et }(v_n)\) nous avons :
\(\left\(v_n=u_n+\frac{1}{3}\quad\text{et}\quad v_{n+1}=u_{n+1}+\frac{1}{3}\right)\quad\Longleftrightarrow\quad\left\(u_n=v_n-\frac{1}{3}\quad\text{et}\quad u_{n+1}=v_{n+1}-\frac{1}{3}\right)\)
Comme \(u_{n+1}=4u_n+1\) il s'en suit que :
\(v_{n+1}-\frac{1}{3}=4\times(v_n-\frac{1}{3})+1\quad\Longleftrightarrow\quad v_{n+1}=4v_n-\frac{4}{3}+1+\frac{1}{3}=4v_n\).
C'est bien une suite géométrique et sa raison \(q=4\).
\(\quad\)b. On en déduit que : \(v_{n+1}=4\times v_n\) et \(v_0=u_0+\frac{1}{3}=\frac{1}{3}\).
Maintenant, il est possible d'exprimer \(v_n\) en fonction de \(n\) : \(v_n=v_0\times 4^n=\frac{1}{3}\times 4^n\).
Compte tenu de la relation : \(u_n=v_n-\frac{1}{3}\), on exprime ainsi \(u_n\) en fonction de \(n\) :
\(u_n=\frac{1}{3}\times 4^n-\frac{1}{3}=\frac{1}{3}\times\left(4^n-1\right)\).
\(\quad\)c. Un petit rappel : \(pgcd(ka,kb)=k\times pgcd(a,b)\),
\(u_n=\frac{1}{3}\times\left(4^n-1\right)\Leftrightarrow 3u_n=4^n-1\)
\(u_{n+1}=\frac{1}{3}\times\left(4^{n+1}-1\right)\Leftrightarrow 3u_{n+1}=4^{n+1}-1\)
Donc on a : \(pgcd(4^n-1,\ 4^{n+1}-1)=pgcd(3u_n,\3u_{n+1})\)
\(pgcd(4^n-1,\ 4^{n+1}-1)=3\times pgcd(u_n,u_{n+1})=3\times 1=3\).
J'espère avoir utilisé les équivalences à bon escient ?
Encore Merci.
@+
Bonsoir,
Voici un problème sur le thème des suites associé à l’arithmétique.
Je pense avoir rédigé l'essentiel, même si je ne suis très sûr des démonstrations en 2c et 2d.
J'ai facilité la lecture un peu longue avec LaTex, Merci pour la vérification.
1) Déterminer le PGCD de [tex]4^2 - 1[/tex] et de [tex]4^6 - 1[/tex]
2) Soit [tex](u_n)[/tex] la suite définie par :
[tex]\quad\forall n\in\mathbb{N}\quad u_{n+2}=5u_{n+1}-4u_n[/tex] avec [tex]u_0=0[/tex], [tex]u_1=1[/tex]
- a. Calculer [tex]u_2[/tex], [tex]u_3[/tex] et [tex]u_4[/tex],
- b. Démontrer que, [tex]\forall n\in\mathbb{N}[/tex] : [tex]u_{n+1}=4u_n+1[/tex],
- c. Démontrer que, [tex]\forall n\in\mathbb{N}[/tex], [tex]u_n[/tex] est un entier naturel,
- d. En déduire, [tex]\forall n\in\mathbb{N}[/tex], le PGCD de[tex]u_n[/tex] et de [tex]u_{n+1}[/tex].
3) Soit [tex](v_n)[/tex] la suite définie par : [tex]\forall n\in\mathbb{N},\quad v_n = u_n+\frac{1}{3}[/tex]
- a. Démontrer que [tex](v_n)[/tex] est une suite géométrique,
- b. [tex]\forall n\in\mathbb{N}[/tex], exprimer [tex]v_n[/tex], puis [tex]u_n[/tex], en fonction de [tex]n[/tex],
- c. Déterminer, [tex]\forall n\in\mathbb{N}[/tex], le PGCD de [tex]4^n- 1[/tex] et de [tex]4^{n+1}-1[/tex].
_____________________________________________________
1) Rappels utiles : [tex]a^3-b^3=(a-b)(a^2+ab+b^2)[/tex] et [tex]a|b\quad\Longleftrightarrow\quad pgcd(a,b)=a[/tex].
Compte tenu des rappels, on peux répondre à la question : [tex]4^6-1=(4^2)^3-1=(4^2-1)[(4^2)^2+1\times 4^2+1]\quad\Longleftrightarrow\quad pgcd(4^2 - 1,\ 4^6 - 1)=4^2 - 1[/tex].
2) [b]a.[/b] Les premiers termes de [tex](u_n)[/tex] sont :
[tex]u_0=0,\ u_1=1,\ u_2=5,\ u_3=21,\ u_4=85[/tex].
[tex]\quad[/tex][b]b.[/b] Démonstration par récurrence :
Initialisation Ok, car [tex]u_1=4\times u_0+1=4\times 0+1=1[/tex],
Récurrence : on suppose [tex]u_{n+1}=4u_n+1\quad\Longleftrightarrow\quad u_{n+1}-1=4u_{n}[/tex] vrai.
Donc par substitution : [tex]u_{n+2}=5u_{n+1}-(u_{n+1}-1)=4u_{n+1}+1[/tex]
Conclusion : la preuve est faite, car [tex]u_{n+2}=4u_{n+1}+1[/tex] est le rang [tex]n+1[/tex] de [tex]u_{n+1}=4u_n+1[/tex].
[tex]\quad[/tex][b]c.[/b] On sait que [tex]u_0=0[/tex] est un entier naturel et je suppose que [tex]u_n=4u_{n-1}+1[/tex] aussi, alors [tex]4\times u_n[/tex] est un entier, de même que [tex]u_{n+1}=4u_{n}+1[/tex] CQFD ?
[tex]\quad[/tex][b]d.[/b] Maintenant que l'on sait qu'il existe des entiers [tex]u_{n+1}[/tex] et [tex]u_n[/tex], grâce au théorème de BEZOUT, on peut affirmer que le [tex]pgcd(u_{n+1},u_n)=1[/tex], puisque [tex]u_{n+1}-4u_{n}=1[/tex] et les coefficients [tex]1[/tex] et [tex]-4[/tex] sont premiers entre eux. CQFD ?
3) [b]a [/b]Concernant la relation entre les suites [tex](u_n)\text{ et }(v_n)[/tex] nous avons :
[tex]\left\(v_n=u_n+\frac{1}{3}\quad\text{et}\quad v_{n+1}=u_{n+1}+\frac{1}{3}\right)\quad\Longleftrightarrow\quad\left\(u_n=v_n-\frac{1}{3}\quad\text{et}\quad u_{n+1}=v_{n+1}-\frac{1}{3}\right)[/tex]
Comme [tex]u_{n+1}=4u_n+1[/tex] il s'en suit que :
[tex]v_{n+1}-\frac{1}{3}=4\times(v_n-\frac{1}{3})+1\quad\Longleftrightarrow\quad v_{n+1}=4v_n-\frac{4}{3}+1+\frac{1}{3}=4v_n[/tex].
C'est bien une suite géométrique et sa raison [tex]q=4[/tex].
[tex]\quad[/tex][b]b.[/b] On en déduit que : [tex]v_{n+1}=4\times v_n[/tex] et [tex]v_0=u_0+\frac{1}{3}=\frac{1}{3}[/tex].
Maintenant, il est possible d'exprimer [tex]v_n[/tex] en fonction de [tex]n[/tex] : [tex]v_n=v_0\times 4^n=\frac{1}{3}\times 4^n[/tex].
Compte tenu de la relation : [tex]u_n=v_n-\frac{1}{3}[/tex], on exprime ainsi [tex]u_n[/tex] en fonction de [tex]n[/tex] :
[tex]u_n=\frac{1}{3}\times 4^n-\frac{1}{3}=\frac{1}{3}\times\left(4^n-1\right)[/tex].
[tex]\quad[/tex][b]c.[/b] Un petit rappel : [tex]pgcd(ka,kb)=k\times pgcd(a,b)[/tex],
[tex]u_n=\frac{1}{3}\times\left(4^n-1\right)\Leftrightarrow 3u_n=4^n-1[/tex]
[tex]u_{n+1}=\frac{1}{3}\times\left(4^{n+1}-1\right)\Leftrightarrow 3u_{n+1}=4^{n+1}-1[/tex]
Donc on a : [tex]pgcd(4^n-1,\ 4^{n+1}-1)=pgcd(3u_n,\3u_{n+1})[/tex]
[tex]pgcd(4^n-1,\ 4^{n+1}-1)=3\times pgcd(u_n,u_{n+1})=3\times 1=3[/tex].
J'espère avoir utilisé les équivalences à bon escient ?
Encore Merci.
@+
