Cours et code réalisé par Vincent Maffet
Soit a et b deux entiers relatifs non nuls, tels que PGCD(a;b)=d. Alors il existe deux entiers relatifs u et v tels que au+bv=d
Dans le cas où a>0 et b>0
- Si b divise a, PGCD(a;b)=b en prenant u=0 et v=1, au+bv=b
- Si a divise b, PGCD(a;b)=a en prenant u=1 et v=0, au+bv=a
- Dans les autres cas, en supposant 0<b<a par exemple, l'algorithme d'Euclide s'écrit : a=bq0+r0 ; b=q1r0+r1 ; r0=q2r1+r2; ..... ; rn-1=qnrn avec 0<rn<rn-1<...<r0<b
On obtient alors : - a-bq0=r0=au0+bv0 avec u0=1 et v0=q0
b-r0q1=r1=b-(a-bq0)q1 soit -aq1+b(1+q1q0)=r1=au1+bv1 avec u1=-q1 et v1=1+q1q0
|
Ainsi de suite, on montre que les restes rk avec 0<k≤n, s'écrivent sous la forme rk=auk+bvk où uk et vk s'écrivent en fonction de q0, q1, ..., qn et en particulier le dernier reste rn qui est le PGCD(a;b)
- Si a<0 et b>0 d=PGCD(-a;b)
- Si a>0 et b<0 d=PGCD(a;-b)
- Si a<0 et b<0 d=PGCD(-a;-b)
Le couple (u;v) n'est pas unique
Soit a et b deux entiers relatifs non nuls, a et b sont premiers entre eux si et seulement S'il existe des entiers relatifs u et v tels que au+bv=1
- Si a et b sont premiers entre eux, alors PGCD(a;b)=1, l'identité de Bezout permet alors de dire qu'il existe des entiers relatifs u et v tels que au+bv=1
- Réciproquement, s'il existe des entiers relatifs tels que au+bv=1 alors le PGCD(a;b) divise 1 [le PGCD(a;b) divise a et b donc divise au+bv]. Le PGCD(a;b) est un entier positif diviseur de 1, c'est donc 1. D'où a et b sont premiers entre eux.
Soit a, b et c 3 entiers relatifs non nuls, si a est premier avec c alors PGCD(a;bc)=PGCD(a;b)
Soit d∈N*
- Si d divise a et b, alors d divise a et bc
-Réciproquement, a et c sont premiers entre eux donc il existe des entiers relatifs u et v tels que au+cv=1
Alors aub+cvb=b, soit a(ub)+(bc)v=b
Donc si d divise a et bc donc d divise b et a
Les diviseurs communs à a et b sont les diviseurs communs à a et bc
Donc PGCD(a;b)=PGCD(a;bc)
-
Partagez ce cours !
Suivez Vincent Maffet sur google + ( cours inspiré de celui fait par le professeur de la classe)