« Arithmétique/PGCD » : différence entre les versions

<math>(a,b) \in \N^{*2}</math><br />Si des entiers naturels q et r, avec <math>r \ne 0\,</math>, sont tels que <math>a = bq+r\,</math>, alors :<br /><math>pgcd(a,b) = pgcd(b,r)\,</math>

d désigne un diviseur commun à a et b. De <math>r = a-bq\,</math>, on en déduit que d divise r. Ainsi tout diviseur commun à a et b est un diviseur commun à b et r.<br />Réciproquement, d' désigne un diviseur commun à b et r. De <math>a = bq+r\,</math>, on déduit que d' divise a. Ainsi tout diviseur commun à b et r est un diviseur commun à a et b.<br />En conclusion, a et b ont les mêmes diviseurs communs que b et r donc <math>pgcd(a,b) = pgcd(b,r)\,</math>

Soient <math>(a,b)\in \N^{*2}</math> tels que <math>a>b\,</math>

! Opération !! Reste <math>r\,</math> !! Commentaire

| on divise <math>a\,</math> par <math>b\,</math>

| <math>r_0\,</math>

| si <math>r_0\neq 0</math>, on divise <math>b\,</math> par <math>r_0\,</math>

| <math>r_1\,</math>

| si <math>r_n\neq 0</math>, on divise <math>r_{n-1}\,</math> par <math>r_n\,</math>

| <math>0\,</math>

| <math>pgcd(r_{n-1},r_n)=r_n\,</math>

| titre = Calcul de <math>pgcd(12000,32000)\,</math>

Donc <math>pgcd(12000,32000)=1000\times pgcd(12,32)=4000.\,</math>

'''Conséquence : ''' si <math>k\,</math> est un entier naturel non nul, diviseur commun à <math>a\,</math> et <math>b\,</math>, alors <math>pgcd\left (\frac{a}{k},\frac{b}{k}\right )=\frac{1}{k}\times pgcd(a,b).</math>

<math>a\,</math> et <math>b\,</math> désignent deux entiers relatifs non nuls. Le PGCD de <math>a\,</math> et <math>b\,</math> est égal au PGCD de <math>|a|\,</math> et <math>|b|\,</math>, c'est-à-dire <math>pgcd(a,b)=pgcd(|a|,|b|).\,</math>

* Les diviseurs communs à <math>a\,</math> et <math>b\,</math> sont encore les diviseurs de <math>pgcd(a,b)\,</math>

Dire que deux entiers relatifs non nuls <math>a\,</math> et <math>b\,</math> sont premiers entre eux signifie que <math>pgcd(a,b)=1.\,</math>

<math>35\,</math> et <math>26\,</math> sont premiers entre eux, car leur seul diviseur commun positif est 1.

Si <math>d=pgcd(a,b)\,</math> alors il existe des entiers relatifs <math>a'\,</math> et <math>b'\,</math> premiers entre eux tels que <math>a=da'\,</math> et <math>b=db'\,</math>.

<math>d|a \Rightarrow \exists a'\in \Z</math> tel que <math>a=da'\,</math>. De même, <math>\exists b'\in \Z</math> tel que <math>b=db'\,</math>.