Coefficient de bézout et calcul matriciel
Posté : lun. 5 mai 2014 21:59
Bonjour je bloque à mon exercice de spé math et je voudrais un peu d'aide pour pouvoir le continuer .Voici l'énoncer un peu long ^^.
Soit a et b deux entiers tels que 0<b<a , b ne divisant pas a . On pose d=pgcd(a;b).
On sait qu'il existe u et v entiers relatis tels que au+bv=d et qu'lon peut rouver u et v en écrivant successivement tous les restes trouvés dans l'algorithme d'euclide comme combinaison linéaire de a et de b jusqu'au (dernier entier reste non nul),r(n) qui est égal a d .
On notera dans la suite ro=a,r1=b.
On effectue les divisions euclidiennes succesives:
ro=r1q1+r2 avec 0=<r2<r1
r1=r2q2+r3 avec 0=<r3<r2
...
rn-2=r(n-1)q(n-1)+r(n) avec0=<rn<rn-1, ou r(n) est le dernier reste non nul donc rn=d
On chercher donc uk et vk entier tels que pour tout k ,
0=<k=<n , r(k)=aU(k)+bV(k).
1.Montrer que u0=1 et v0=0 et déterminer u1 et v1
2.Soit k tel que 1=<kwn
Exprimer uk+1 en fonction de Uk-1 et Uk et Vk+1 en fonction de Vk-1 et Vk.
3. Soit Mk la matrice
(Uk-1 ; Vk-1)
(Uk ; Vk )
a. Ecrire M1
b.Montrer que Mk+1=Pk*Mk ou Pk = ( 0 ; 4 )
(1 ; -q(k))
Pour tout k ,1=<k=<n-1
4.
a.Ecrire l'algorithme d'euclide pour a=204 et b=32
b.Déterminer les matrice Mk et Pk successives jusqu'a obtenir Un et Vn .
c.Vérifier les résultats obtenus .
5.
Désuide de ce qui pécède un algorithme qui demande a et b (c<b<a) teste si b divise a , et si ce n'est pas le cas affiche des coefficient u et v telque d=au+bv
Pour le 1. J'ai fais comme ceci.
r0=aU(0)+bV(0) or r0=a donc les solutions sont U(0)=1 et V(0)=0 et pour k=1 r1=aU(1)+bV(1) et r1=b donc r1=aU(1)+bV(1) donc les solutions sont U1=0 et V1=1 . C'est aprés que je bloque donc dans le 2. Je solicite donc l' aide a tout ceux qui voudront bien m'aider et je les eremmercie d'avance.
Soit a et b deux entiers tels que 0<b<a , b ne divisant pas a . On pose d=pgcd(a;b).
On sait qu'il existe u et v entiers relatis tels que au+bv=d et qu'lon peut rouver u et v en écrivant successivement tous les restes trouvés dans l'algorithme d'euclide comme combinaison linéaire de a et de b jusqu'au (dernier entier reste non nul),r(n) qui est égal a d .
On notera dans la suite ro=a,r1=b.
On effectue les divisions euclidiennes succesives:
ro=r1q1+r2 avec 0=<r2<r1
r1=r2q2+r3 avec 0=<r3<r2
...
rn-2=r(n-1)q(n-1)+r(n) avec0=<rn<rn-1, ou r(n) est le dernier reste non nul donc rn=d
On chercher donc uk et vk entier tels que pour tout k ,
0=<k=<n , r(k)=aU(k)+bV(k).
1.Montrer que u0=1 et v0=0 et déterminer u1 et v1
2.Soit k tel que 1=<kwn
Exprimer uk+1 en fonction de Uk-1 et Uk et Vk+1 en fonction de Vk-1 et Vk.
3. Soit Mk la matrice
(Uk-1 ; Vk-1)
(Uk ; Vk )
a. Ecrire M1
b.Montrer que Mk+1=Pk*Mk ou Pk = ( 0 ; 4 )
(1 ; -q(k))
Pour tout k ,1=<k=<n-1
4.
a.Ecrire l'algorithme d'euclide pour a=204 et b=32
b.Déterminer les matrice Mk et Pk successives jusqu'a obtenir Un et Vn .
c.Vérifier les résultats obtenus .
5.
Désuide de ce qui pécède un algorithme qui demande a et b (c<b<a) teste si b divise a , et si ce n'est pas le cas affiche des coefficient u et v telque d=au+bv
Pour le 1. J'ai fais comme ceci.
r0=aU(0)+bV(0) or r0=a donc les solutions sont U(0)=1 et V(0)=0 et pour k=1 r1=aU(1)+bV(1) et r1=b donc r1=aU(1)+bV(1) donc les solutions sont U1=0 et V1=1 . C'est aprés que je bloque donc dans le 2. Je solicite donc l' aide a tout ceux qui voudront bien m'aider et je les eremmercie d'avance.