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

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

| <math>0\le r_0<b \mboxtext{ et } \operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r_0)</math>

| <math>0\le r_1<r_0 \mboxtext{ et } \operatorname{pgcd}(b,r_0)=\operatorname{pgcd}(r_0,r_1)</math>

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

<math>\operatorname{pgcd}(ka,kb) = k\times \operatorname{pgcd}(a,b).</math>.</center>

L'entier ''k'' divise ''ka'' et ''kb'' donc aussi leur PGCD. L'entier ''d'' > 0 défini par ''pgcd''(''ka'', ''kb'') = ''kd'' vérifie alors :<center>

<center><math>\forall n\in\Z\quad n\mid a,b\iff kn\mid ka,kb\iff kn\mid pgcd(ka,kb)\iff n\mid d</math></center>

donc<center>

<center><math>\operatorname{pgcd}(a,b)=d=\operatorname{pgcd}(ka,kb)/k.</math>.</center>

| titre =Exemple Calcul: calcul de <math>\operatorname{pgcd}(12000,32000)</math>

:<math>12000=12\times 1000times1000</math> et <math>32000=32\times 1000times1000</math>

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

<math>a</math>Le etPGCD <math>b</math> désignentde deux entiers relatifs non nuls. Le PGCD de <math>a</math> et <math>b</math> est égal aule PGCD de <math>|a|</math>leurs etvaleurs <math>|b|</math>absolues, c'est-à-dire <math>\operatorname{pgcd}(a,b)=\operatorname{pgcd}(|a|,|b|).</math>.

* <math>\forall k \in \Z^*, \quad\operatorname{pgcd}(ka,kb)=|k|\operatorname{pgcd}(a,b)</math>

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

Dire que deuxDeux entiers relatifs non nuls <math>a</math> et <math>b</math> sont dits premiers entre eux signifie quesi <math>\operatorname{pgcd}(a,b)=1.</math>.

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

Soient <math>(a,b)\in \Z^{*2}</math>, et <math>db</math> ledeux PGCDentiers derelatifs non nuls, <math>ad</math> etleur <math>b</math>PGCD, et <math>a',b'</math> les entiers définis par <math>a=da'</math> et <math>b=db'</math>. Alors, <math>a'</math> et <math>b'</math> sont premiers entre eux.

*<math>\operatorname{pgcd}(a',b')=\frac{\operatorname{pgcd}(da',db')}d=\frac{\operatorname{pgcd}(a,b)}d=1</math>.