1- Rappels concernant le PGCD et le PPCM de deux entiers relatifs

1.1 Définition du PGCD

Soient \(a\) et \(b\), deux entiers relatifs. Notons \(D(a)\) et \(D(b)\) respectivement l'ensemble des diviseurs de \(a\) et l'ensemble des diviseurs de \(b\). On définit alors le PGCD de \(a\) et \(b\) comme : $$ PGCD(a,b) = \max \left( D(a) \cap D(b) \right)$$ Comme \(1\) divise n'importe quel entier relatif, quelque soient \(a\) et \(b\), on aura toujours \(1 \in D(a)\) et \(1 \in D(b)\). Si bien que \(D(a) \cap D(b)\) n'est jamais l'ensemble vide. D'après la définition que l'on vient de donner (qui peut changer selon les auteurs) le PGCD de deux entiers relatifs est toujours un nombre positif supérieur ou égal à \(1\). Ainsi l'algorithme d'Euclide, nous fournit le PGCD au signe près.

1.2 Définition du PPCM

Soient \(a\) et \(b\), deux entiers relatifs. Notons \(M(a)\) et \(M(b)\) respectivement l'ensemble des multiples strictement positifs de \(a\) et l'ensemble des multiples strictement positifs de \(b\). On définit alors le PPCM de \(a\) et \(b\) comme : $$ PPCM(a,b) = \min \left( M(a) \cap M(b) \right)$$ Comme \(ab\) est multiple de \(a\) mais aussi de \(b\), on aura toujours \(ab \in M(a)\) et \(ab \in M(b)\). Si bien que \(M(a) \cap M(b)\) n'est jamais l'ensemble vide et possède donc un minimum.

2- Propriété liant le PGCD et le PPCM

Nous avons la proriété suivante :
Soient \(a\) et \(b\) des nombres entiers relatifs non-nuls, alors, nous avons : $$ PPCM(a,b) PGCD(a,b) = \left| ab \right| $$

Démonstration

Si \(a\) et \(b\) sont premiers entre eux, alors on a : \(PGCD(a,b) = 1\) et \(PPCM(a,b) = \left|ab \right|\) puisque \(a\) et \(b\) n'ont aucun facteur premier commun. On a ainsi l'égalité.

Si \(a\) et \(b\) ne sont pas premiers entre eux, alors \(\frac{a}{PGCD(a,b)}\) et \(\frac{b}{PGCD(a,b)}\) sont premiers entre eux en général. Si bien que : $$PPCM \left( \frac{a}{PGCD(a,b)}, \frac{b}{PGCD(a,b)} \right) = \frac{ab}{PGCD(a,b)^2} $$ On a alors d'après les propriétés du PPCM : $$PPCM \left( a, b \right) = \frac{ab}{PGCD(a,b)} $$

3- Le théorème de Bézout

3.1 Propriété de Bézout

Soient \(a\) et \(b\), deux entiers relatifs. Il existe \(u\) et \(v\) deux entiers relatifs tels que \(au + bv = PGCD(a,b)\)

Démonstration

Si \(a\) et \(b\) sont tous les deux nuls, l'identité est évidente.

Sinon \(PGCD(a,b)\) est strictement positif, et dans ce cas, l'ensemble des combinaisons linéaires strictement positives de \(a\) et \(b\) qui contient au moins \(a^2 + b^2 \) est non-vide. Cet ensemble possède donc un plus petit élément que l'on peut noter \(\alpha_0 \). Il existe donc \(u_0\) et \(v_0\) tels que \(\alpha_0 = au_0 + b v_0 \).

Puisque \(PGCD(a,b)\) divise \(a\) et divise \(b\), il divise à fortiori \(\alpha_0\).

Réciproquement, soient \(u\) et \(v\) des entiers relatifs. La division euclidienne de \(au + bv \) par \(\alpha_0\) donne : $$ au + bv = q \alpha_0 + r $$ Avec \(q\) un entier relatif et \(r\), le reste de la division euclidienne, c'est-à-dire, un entier positif plus petit que \(\alpha_0\). D'où : $$ au + bv = q (au_0 + bv_0) + r$$ $$ r = a(u - qu_0) + b(v-qv_0) $$ \(r\) étant une combinaison linéaire de \(a\) et \(b\) positive et strictement plus petite que \(\alpha_0\), on a d'après la définition de \(\alpha_0 \), que \(r = 0\). Donc \(au + bv = q \alpha_0\). D'où \(\alpha_0\) divise \(au + bv\) pour n'importe quelles valeurs de \(u\) et \(v\) donc en particulier, il divise \(a\) et il divise \(b\). Et donc \(\alpha_0\) divise \(PGCD(a,b)\). On a alors que \(\alpha_0 = PGCD(a,b)\).

3.2 Réciproque partielle

Soient \(a\) et \(b\) deux entiers relatifs. Soit \(d\) un diviseur commun positif de \(a\) et de \(b\). Si il existe deux entiers relatifs \(x\) et \(y\) tels que \(ax + by = d\) alors \(d = PGCD(a,b)\).

Démonstration

En effet, si \(d = ax + by \) alors tout diviseur commun de \(a\) et \(b\) divise \(d\). Comme \(d\) est positif, c'est effectivement le plus grand commun diviseur de \(a\) et \(b\).

4- Formule sommatoire de Polezzi pour le PGCD

Soient \(a\) et \(b\) deux entiers positifs, on a que (\(E\) désignant la fonction partie entière et les accolades, la partie fractionnaire): $$PGCD(a,b) = a + b - ab + 2 \sum_{k=1}^{b-1} E \left( \frac{ka}{b} \right) $$

Démonstration

On pose : \(a = a' PGCD(a,b) \) et \(b = b' PGCD(a,b)\) avec \(a'\) et \(b'\) des nombres premiers entre eux. \(\frac{ka}{b} = \frac{ka'}{b'} \) est un entier, si et seulement si \(b'\) divise \(k\). Pour \( k \) parcourant l'intervalle d'entiers jusqu'à \(b-1\), le nombre de fois où \( b' \) divise \(k\) correspond au nombre de multiples de \(b'\) dans l'intervalle d'entiers \(\left[b', b-1 \right]\) ce qui correspond exactement à \(E \left( \frac{b-1}{b'} \right) = E \left( d - \frac{1}{b'} \right) = PGCD(a,b) - 1\).

De plus, nous avons que :
Si \(\frac{ka}{b}\) est un entier alors \( E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) = a \).
Si \(\frac{ka}{b}\) n'est pas un entier alors \( E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) = a - \left\{ \frac{ka}{b} \right\} - \left\{ a - \frac{ka}{b} \right\} = a - 2 \left\{ \frac{ka}{b} \right\}\). Et comme \( E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) \) est un entier, soit \( 2 \left\{ \frac{ka}{b} \right\} \) vaut \(0\) soit il vaut \(1\) mais comme \( \frac{ka}{b}\) n'est pas un entier alors il ne peut pas valoir \(0\). D'où : $$ E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) = a - 1$$

On a alors que : $$ \sum_{k=1}^{b-1} \left( E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) \right) = a(PGCD(a,b) - 1) + (a - 1)(b - 1 - (PGCD(a,b) - 1)) $$ $$ \sum_{k=1}^{b-1} \left( E \left( \frac{ka}{b} \right) + E \left(a - \frac{ka}{b} \right) \right) = ab - a - b + PGCD(a,b) $$ $$ \sum_{k=1}^{b-1} E \left( \frac{ka}{b} \right) + \sum_{k=1}^{b-1} E \left((b-k) \frac{a}{b} \right) = ab - a - b + PGCD(a,b) $$ Et dans par le changement d'indice dans la deuxième somme \( k' = b - k \), on obtient le résultat voulu : $$ 2 \sum_{k=1}^{b-1} E \left( \frac{ka}{b} \right) = ab - a - b + PGCD(a,b) $$