Forum de mathématiques - Bibm@th.net

CIRDECO

Invité

suites - pgcd

Bonjour,
on a u(n) et v(n) deux suites avec u(0)=58 et v(0)=52 et telles que :
u(n+1)=u(n)+v(n) et v(n+1)=u(n)-v(n)
1) calculer par l'algorithme d'Euclide PGCD(58;52).
Je trouve  2 car
58 = 52*1+6
52=6*8+4
6=4*1+2
4=2*2+0 et le dernier reste non nul est 2
2)Montrer que pour tout n entier naturel, tout diviseur commun de u(n) et v(n) est un diviseur commun de u(n+1) et de v(n+1).
Nous savons que si a divise b et a divise c (a diviseur commun de a et c) alors a divise b+c et b-c et le résultat en découle.
3)Qu'en déduire pour PGCD(u(n);v(n)) et PGCD(u(n+1);v(n+1)) ?
D'après 2), l'ensemble des diviseurs de u(n) et v(n) est contenu dans l'ensemble des diviseurs de u(n+1) et v(n+1) donc on a :
PGCD(u(n);v(n)) <= PGCD(u(n+1);v(n+1)) ou encore PGCD(u(n);v(n)) divise PGCD(u(n+1);v(n+1)).
Mais a-t-on l'égalité ?
je n'arrive pas à l'établir ....
Merci,
Cédric

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : suites - pgcd

Bonjour

pour n=0 puis 1, puis 2 : exprimez  [tex]u_n\ et\ v_n[/tex] en fonction de r et s premiers entre eux,
et établissez que le PGCD est multiplié par 2 quand n augmente de 2...

Dico

Membre

Inscription : 12-12-2009

Messages : 120

Re : suites - pgcd

Bonjour Cédric
3-) Erreur de langage. tu devrais plutôt dire: l'ensemble des diviseurs commun à [tex]u_n[/tex] et [tex]v_n[/tex] est contenu dans l'ensemble des diviseurs commun à [tex]u_{n+1}[/tex] et [tex]v_{n+1}[/tex].
Non il n'y a égalité, et ceci parce que [tex]PGCD(u_{0},v_{0})=2[/tex].
En effet, si [tex]\delta=PGCD(u_{n+1},v_{n+1})[/tex] alors, [tex]\delta[/tex] divise [tex]u_{n+1}+v_{n+1}[/tex] et [tex]u_{n+1}-v_{n+1}[/tex]. i.e.,  [tex]\delta[/tex] divise [tex]2u_n[/tex] et [tex]2v_n[/tex]. Or, [tex]\delta[/tex] et [tex]2[/tex] ne sont pas prémier entre eux ([tex]\delta[/tex] sera toujours pair). On ne peut donc pas conclure (en utilisant Gauss) que [tex]\delta[/tex] divise [tex]u_n[/tex] et [tex]v_n[/tex].
Comme contre exemple, regardes  [tex]PGCD(u_{1},v_{1})[/tex] et  [tex]PGCD(u_{2},v_{2})[/tex].

Bon après midi!

CIRDECO

Invité

Re : suites - pgcd

Bonsoir,
Merci pour l'éclaircissement de la non-égalité :
Je trouve PGCD(u(0);v(0))=PGCD(u(1);v(1))=2
PGCD(u(2);v(2))=PGCD(u(3);v(3))=4
PGCD(u(4);v(4))=PGCD(u(5);v(5))=8
Il semblerait que si n est pair, PGCD(u(n);v(n)) = PGCD(u(n+1);v(n+1)).
Comment le prouver ?
Merci,
Cédric

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : suites - pgcd

Bonsoir,

@ CIRDECO : par récurrence...

CIRDECO

Invité

Re : suites - pgcd

Bonsoir,
Je trouve finalement :
PGCD(u(n+2);v(n+2))=2PGCD(u(n);v(n))
PGCD(u(n+3);v(n+3))=2PGCD(u(n+1);v(n+1))
et nous pouvons donc calculer tous les PGCD sachant que PGCD(u(0),v(0))=PGCD(u(1);v(1))=2.
Je pense que le problème est résolu même si la question 3) me semble toujours bizarre.
MERCI POUR VOTRE AIDE
Cordialement,
Cédric

CIRDECO

Invité

Re : suites - pgcd

bonjour,
j'ai compris :
par récurrence :
si n est pair : PGCD(u(n);v(n)) = PGCD(u(n+1);v(n+1)).
si n est impair :2PGCD(u(n);v(n)) = PGCD(u(n+1);v(n+1)).
Est-ce bien correct ?
Merci d'approuver (ou non).
Cédric

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : suites - pgcd

bonjour,

il est bon de donner explicitement les bases de la récurrence :
u(0) = 2 x 29,  v(0)=2 x 26 : 29 et 26 sont premiers entre eux
u(1) = 2 x (29 + 26) = 2 x 55,  v(1) = 2 x (29 - 26) = 2 x 3 : 55 et 3 sont premiers entre eux
u(2) = 2 x (55 + 3)= 2² x 29,  v(2) = 2 x (55 - 3) = 2² x 26

pour pouvoir définir la récurrence :
Pour tout p et n=2p (n pair), si [tex]u(n) = 2^{p+1} \times 29\ et\ v(n) = 2^{p+1} \times 26[/tex]
      alors [tex]u(n+1) = 2^{p+1} \times 55\ et\ v(n+1) = 2^{p+1} \times 3[/tex]
Pour tout p et n=2p+1 (n impair), si [tex]u(n) = 2^{p+1} \times 55\ et\ v(n) = 2^{p+1} \times 3[/tex]
       alors [tex]u(n+1) = 2^{p+2}\times 29\ et\ v(n+1) = 2^{p+2}\times 26[/tex]
et conclure :
comme c'est vrai pour p=0, c'est vrai pour tout p positif ou nul donc vrai pour tout n positif ou nul

et le PGCD est bien mis en évidence en fonction de p (et n)
A+

CIRDECO

Invité

Re : suites - pgcd

Bonsoir,
Merci pour ces précisions !
Tout est clair !
Très cordialement,
Eric