Spécialité maths PGCD

[Zyro]

Bonjour, je suis bloqué sur une partie d'un de mes DM de maths : je vais vous réécrire ce que j'ai fais pour le moment, pour que vous compreniez mieux.

Soit (Un) la suite définie par U0 = 0 ; U1 = 1 ; Un+2 = 3(Un+1) - 2Un

1. calculer U2, u3 et u4.
   u2 = 3
   u3 = 7
   u4 = 15
   2)a) Démontrer par récurrence que pour tout n ∈ $mathbbN$, Un+1 = 2Un + 1
   Fait.
   b) Démontrer grâce au théorème de Bézout que pour n ∈ $mathbbN$, PGCD(Un+1;Un)=1
   Fait.
   3)a) Démontrer par récurrence que, pour tout n ∈ $mathbbN$, Un = $2^n$ -1
   Fait.
   b) Vérifier que, pour tout couple (n;p) ∈ $mathbbN$², Un+p = Un(Up +1) + Up
   Là je sais pas trop si je dois faire une récurrence ou pas, et si oui, comment je dois procéder.
   c) En déduire que PGCD(Un;Up) divise Un+p et donc que PGCD(Un;Up) divise PGCD(Un;Un+p).
   Montrer de même que PGCD (Un;Un+p) divise PGCD(Un;Up). On a donc PGCD(Un;Un+p) PGCD(Un;Up) (1)
   Je pense que je dois faire cette question avec une partie de la réponse précédente, mais je vois pas trop comment ...
2. Soient a,b,q,r ∈ $mathbbN$* tels que a =bq + r avec 0 ≤ r < 1
   a) Justifier comment en répétant l'égalité (1) un certain nombre de fois, on trouve PGCD (ub;ur) = PGCD (ub;ua)
   Ba je vois pas comment faire
   b) En utilisant ce qui précède et l'algorithme d'Euclide, justifier que PGCD(Ub;Ua) = Upgcd(a;b)
   pareil ..

Pour le reste de l'exercice, j'ai réussi, mais je vois pas comment faire pour les questions 3) b et 3)c), et aussi pour les 4)a) et 4)b).
Merci d'avance ..

[jacam.coline]

J'ai le même DM et j'aimerais savoir si tu pouvais me donner le corrigé que tu as du avoir, parce que j'avoue que je suis aussi coincée... je n'ai fais que les questions, 1) 2) 3)a et b

[Zyro]

Je n'ai pas encore reçu le corrigé

[mtschoon]

Bonjour !

Un corrigé est donc attendu ? ? ? ? ? ? ? ? ? ? ? ? ! ! ! ! ! ! ! ! !

Vous faites donc l'exercice avec un corrigé .......................

Une piste pour le 3)b) ( en attendant le fameux corrigé.)

Une démonstration directe possible :

$u_{n+p}=2^{n+p}-1$

En transformant pour arriver au résultat .

$u_{n+p}=2^{n+p}-2^p+2^p-1=2^p(2^n-1)+2^p-1$

En transformant encore un peu :

$u_{n+p}=(2^p-1+1)(2^n-1)+2^p-1$

En revenant à U :

$u_{n+p}=(u_p+1)u_n+u_p$

CQFD

Bonne suite avec le "corrigé".

[Zyro]

J'ai réussi le 3)b), et je n'aurais le corrigé que dans 1 semaine, après avoir rendu le DM. C'est pour celà que j'ai besoin d'aide