Les propriétés du PGCD de deux entiers naturels

Pour tout $ (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b $, on note :

$ \delta = a \wedge b = PGCD(a, b) $;

Le $ PGCD(a, b) $ est le plus grand diviseur commun à $ a $ et $ b $.

C'est le dernier reste $ R_n $ non nul de la division euclidienne de $ a $ par $ b $ dans l'algorithme d'Euclide .
$ \mathcal{D}(a, b)$ l'ensemble des diviseurs communs à $ a $ et à $ b $;
$ \mathcal{D}(\delta)$ l'ensemble des diviseurs de $ PGCD(a, b) $.

Égalité entre les PGCD successifs de l'algorithme d'Euclide

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace a > b, \enspace \forall R \in \mathbb{N^*}, \enspace 0 < R < b, $$

$$ a = bq + R \Longrightarrow PGCD(a, b) = PGCD(b, R) $$

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b,$$

$$ \exists! r \in \mathbb{N}^*, \enspace \exists! (p_1 < p_2 < ... < p_r) \in \mathbb{P}^r, \enspace \exists (\alpha_1, \alpha_2, ..., \alpha_r) \in \mathbb{N}^r, \enspace \exists (\beta_1, \beta_2, ..., \beta_r) \in \mathbb{N}^r, $$

$$ PGCD(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_2^{min\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{min \{ \alpha_r, \beta_r\}} $$

Identité de Bézout

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.04em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (\text{Identité de Bézout})$$

Décomposition de deux nombres en lien avec leur PGCD

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (a', b') \in \mathbb{N}, \enspace \begin{cases} a = \delta a' \\ b = \delta b' \end{cases}\enspace \enspace (\text{avec } a' \wedge b' = 1)$$

Égalité entre les diviseurs de a et de b et les diviseurs de leur PGCD

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, $$

$$ \mathcal{D}(a, b) = \mathcal{D}\bigl( PGCD(a, b) \bigr) $$

L'ensemble des diviseurs communs à $ a $ et à $ b $ est l'ensemble des diviseurs de $ PGCD(a, b) $.

Linéarité

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, \enspace \forall k \in \mathbb{Z},$$

$$ PGCD(ka, kb) = k.PGCD(a, b) $$

Lien entre PGCD et PPCM

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b,$$

$$ PGCD(a, b) \times PPCM(a, b) = ab $$

Récapitulatif des propriétés du PGCD

Démonstrations

Égalité entre les PGCD successifs de l'algorithme d'Euclide

Soient $(a, b) \in \hspace{0.04em}\mathbb{N}^2$ deux entiers naturels.

Si $b$ ne divise pas $a$, on sait que :

$$ \exists q_0 \in (\mathbb{N}), \enspace \exists R_0 \in \mathbb{N^*}, \enspace 0 < R_0 < b, \enspace a = bq_0 + R_0 $$

De même, si $R_0$ ne divise pas $b$ :

$$ \exists q_1 \in (\mathbb{N}), \enspace \exists R_1 \in \mathbb{N^*}, \enspace 0 < R_1 < R_0 , \enspace b = R_0 q_1 + R_1 $$

Et ainsi de suite...

Or, on sait par l'algorithme d'Euclide que :

$ \forall (k,n) \in \hspace{0.04em}\mathbb{N}^2$, pour $ k $ allant de $ 0 $ à $ n $, tant que $R_{k} $ ne divise pas $R_{k -1 } $, c'est-à-dire tant que $R_{k} \neq 0$ :

$$ PGCD(a, b) = PGCD(b, R_0) = PGCD(R_0, R_1) = \enspace ... \enspace = PGCD(R_{n - 1}, R_n) = R_n \neq 0$$

Soit finalement :

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace a > b, \enspace \forall R \in \mathbb{N^*}, \enspace 0 < R < b, $$

$$ a = bq + R \Longrightarrow PGCD(a, b)= PGCD(b, R) $$

Décomposition en facteurs premiers

Soient $ (a, b) \in \hspace{0.04em}\mathbb{N}^2 $ deux entiers naturels avec $a > b $.

Soit la décomposition de $a $ et de $b $ en facteurs premiers :

$$ \begin{cases} a = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r} \\ b = p_1^{\beta_1}p_2^{\beta_2}\dots p_r^{\beta_r} \end{cases}$$

On sait que $ PGCD(a, b) $ est le plus grand diviseur commun à $a $ et à $ b $.

Le plus grand diviseur commun $D$ à deux puissances d'un même nombre premier $ A = p^{\alpha} $ et $ B = p^{\beta} $ est donné par la plus petite de ces deux puissances :

$$ D = p^{\min \{ \alpha, \beta\}} $$

Généralisation par indépendance des facteurs

Tout diviseur $ d $ commun à $ a $ et $ b $ ne peut être composé que des mêmes facteurs premiers $ p_i $. De plus, en raison de l'unicité de la décomposition en facteurs premiers, le choix de l'exposant maximal pour un facteur $ p_i $ n'influence pas le choix des exposants pour les autres facteurs distincts.

Ainsi, maximiser le diviseur commun $ d $ revient à maximiser simultanément et de manière indépendante l'exposant de chaque nombre premier $ p_i $, ce qui impose de prendre séparément le minimum des exposants $ \min\{\alpha_i, \beta_i\} $ pour chaque composante primaire.

Alors, en appliquant ce raisonnement à l'ensemble des facteurs premiers de la décomposition de $ a $ et de $ b $, on obtient par produit :

$$ PGCD(a, b) = p_1^{\min \{ \alpha_1, \beta_1\}} \times p_2^{\min\{\alpha_2, \beta_2\}} \times \dots \times p_r^{\min \{ \alpha_r, \beta_r\}} $$

Identité de Bézout

Soient $(a, b) \in \hspace{0.04em}\mathbb{Z}^2$ deux entiers relatifs avec $a > b $.

Partons de notre hypothèse que $ \delta = a \wedge b $.

Deux cas de figure se présentent alors : $ b \mid a $ ou $ b \nmid a $.

si $ b $ divise $ a $

Si $ b $ divise $ a $, alors $\exists q \in \mathbb{N}$, tel que $ q < a$,

$$ a = bq \Longrightarrow a \wedge b = b $$

On remarque alors que $ \delta = b $ et peut s'écrire sous la forme :

$$ \delta = au + bv, \text{ avec } \begin{cases} u = 0\\ v = 1 \end{cases}$$
si $ b $ ne divise pas $ a $

Dans ce cas, $ \exists q_0 \in \mathbb{Z}, \enspace \exists R_0 \in \mathbb{N}, \enspace 0 < R_0 < b$,

$$ a = bq_0 + R_0 $$

Or, on sait par la propriété vue plus haut que :

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace \forall R \in \mathbb{N^*}, $$

$$ a = bq + R \Longrightarrow PGCD(a, b) = PGCD(b, R) $$

Soit dans notre cas :

$$ a = bq_0 + R_0 \Longrightarrow a \wedge b = b \wedge R_0 $$
1. si $ R_0 $ divise $ b $
  
  Alors, $ \delta = R_0 $ car $ R_0 $ est le dernier reste non nul de l'algorithme d'Euclide , et :
  
  $$ \delta = R_0 = a - bq_0 $$
  
  $$ \delta = au + bv, \text{ avec } \begin{cases} u = 1\\ v = -q_0 \end{cases}$$
2. si $ R_0 $ ne divise pas $ b $
  
  Alors, $ \exists q_1 \in \mathbb{Z}, \enspace \exists R_1 \in \mathbb{N}, \enspace 0 < R_1 < R_0 $,
  
  $$ b = R_0q_1 + R_1 \Longrightarrow a \wedge b = b \wedge R_0 = R_0 \wedge R_1 $$
  1. si $ R_1 $ divise $ R_0 $
    
    Alors, $ \delta = R_1 $ et :
    
    $$ \delta = R_1 = b - R_0q_1 $$
    
    $$ \delta = R_1 = b - (a - bq_0)q_1 $$
    
    $$\delta = R_1 = -q_1 a + b(1 + q_0 q_1)$$
    
    $$ \delta = au + bv \text{ avec } \begin{cases} u = -q_1 \\ v = -1 + q_0 q_1 \end{cases}$$
  2. - si $ R_1 $ ne divise pas $ R_0 $
    
    On recommence l'algorithme d'Euclide jusqu'à ce que le dernier reste non nul soit le PGCD .

Ainsi, on voit que dans tous les cas de figures :

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.04em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (\text{Identité de Bézout}) $$

Cette propriété est connue sous le nom d' identité de Bézout .

Décomposition de deux nombres en lien avec leur PGCD

Soient $(a, b) \in \hspace{0.04em}\mathbb{Z}^2$ deux entiers relatifs.

Si $ \delta = a \wedge b$, alors $ \delta \mid a $ et $ \delta \mid b $, soit :

$$ \begin{cases} a = \delta a' \\ b = \delta b' \end{cases}$$

Si $ a' $ et $ b' $ n'étaient pas premiers entre eux, on aurait alors l'existence d'un diviseur $ d $, autre que $ 1 $, et tel que :

$$ \begin{cases} a' = d a'' \\ b' = d b'' \end{cases}$$

Ce qui voudrait dire que l'on aurait un diviseur commun $ d $ plus grand que $ \delta $.

Ce qui est absurde, donc $ a' $ et $ b' $ sont nécessairement premiers entre eux.

On a alors impérativement que $a' \wedge b' = 1$.

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \exists (a', b') \in \mathbb{N}, \enspace \begin{cases} a = \delta a' \\ b = \delta b' \end{cases}\enspace \enspace (\text{avec } a' \wedge b' = 1)$$

Soit finalement,

Égalité entre les diviseurs de a et de b et les diviseurs de leur PGCD

Soient $ (a,b) \in (\mathbb{N}^*)^2 $ deux entiers naturels non tous deux nuls, et notons $ \delta = a \wedge b $ leur PGCD.

Nous voulons démontrer que l'ensemble des diviseurs communs à $ a $ et $ b $ est exactement l'ensemble des diviseurs de $ \delta $.

Sens direct : Si $ d $ divise $ a $ et $ b $, alors $ d $ divise $ \delta $

Supposons qu'il existe un entier naturel $ d $ qui soit un diviseur commun à $ a $ et à $ b $. On a donc :

$$ \begin{cases} d \mid a \\ d \mid b \end{cases} $$

D'après l'identité de Bézout démontrée plus haut, il existe un couple d'entiers relatifs $ (u, v) \in \mathbb{Z}^2 $ tel que :

$$ \delta = au + bv $$

Puisque $ d $ divise $ a $ et que $ d $ divise $ b $, alors :

$$ \exists(k, k') \in \mathbb{Z}^2, \ \begin{cases} d \mid a \implies a = kd \\ d \mid b \implies b = k'd \end{cases} $$

En substituant ces expressions dans l'identité de Bézout, on obtient :

$$ \delta = (kd)u + (k'd)v = d(ku + k'v) $$

Comme $ (ku + k'v) $ est un entier relatif, cette égalité montre de façon immédiate que $ d $ divise $ \delta $.

$$ \forall (a,b) \in (\mathbb{N}^*)^2, \enspace \delta = a \wedge b, $$

$$ (d \mid a) \land (d \mid b) \implies d \mid \delta $$
Sens réciproque : Si $ d $ divise $ \delta $, alors $ d $ divise $ a $ et $ b $

Réciproquement, supposons que $ d $ soit un entier naturel qui divise $ \delta $. Par définition du PGCD, $ \delta $ est un diviseur commun à $ a $ et à $ b $, ce qui se traduit par :

$$ d \mid \delta \implies \begin{cases} \delta \mid a \\ \delta \mid b \end{cases} $$

Par transitivité de la relation de divisibilité, on sait que :

$$ \forall (a, b) \in (\mathbb{Z}^*)^2, \enspace \forall c \in \mathbb{Z}, $$

$$ (a \mid b) \text{ et } (b \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c $$

Dans notre cas,

$$ \begin{cases} (d \mid \delta) \text{ et } (\delta \mid a) \hspace{0.2em} \Longrightarrow \hspace{0.2em} d \mid a \\ (d \mid \delta) \text{ et } (\delta \mid b) \hspace{0.2em} \Longrightarrow \hspace{0.2em} d \mid b \end{cases} $$

$$ \forall (a,b) \in (\mathbb{N}^*)^2, \enspace \delta = a \wedge b, $$

$$ d \mid \delta \implies (d \mid a) \land (d \mid b) $$

Le nombre $ d $ est donc bien un diviseur commun à $ a $ et à $ b $.
Conclusion

Les deux implications forment une équivalence :

$$ (d \mid a) \land (d \mid b) \Longleftrightarrow d \mid \delta $$

Un entier $ d $ divise $ a $ et $ b $ si, et seulement si, il divise leur PGCD $ \delta $.

Alors, on a finalement démontré que:

$$ \forall (a,b) \in (\mathbb{N}^*)^2, $$

$$ \mathcal{D}(a, b) = \mathcal{D}\bigl( PGCD(a, b) \bigr) $$

On pourra trouver tous ces diviseurs par décomposition en facteurs premiers du $ PGCD(a, b) $ .

Linéarité

Soient $(a, b) \in \hspace{0.04em}\mathbb{Z}^2$ deux entiers relatifs avec $a > b $, et $k \in \mathbb{Z}$.

Notons $ \delta = PGCD(a, b)$ et $ \Delta = PGCD(ka, kb) $.

On sait par la propriété des diviseurs communs entre deux nombres et leur PGCD que :

L'ensemble des diviseurs communs à $ a $ et à $ b $ est l'ensemble des diviseurs de $ PGCD(a, b) $.

Alors,

$$ \begin{cases} k \mid ka \\ k \mid kb \end{cases}\Longrightarrow k \mid \Delta $$

Si $ k \mid \Delta $, cela signifie aussi que :

$$ \exists c \in \mathbb{Z}, \enspace \Delta = kc $$

De même, comme $ \Delta = PGCD(ka, kb) $, alors :

$$ \begin{cases} \Delta \mid ka \\ \Delta \mid kb \end{cases}$$

Mais $ \Delta = kc $, soit avec la propriété de simplification dans la divisibilité :

$$ \begin{cases} kc \mid ka \Longrightarrow c \mid a \\ kc \mid kb \Longrightarrow c \mid b \end{cases}$$

Et encore avec la propriété des diviseurs communs entre deux nombres et leurs PGCD :

$$ \begin{cases} c \mid a \\ c \mid b \end{cases}\Longrightarrow c \mid \delta $$

Et enfin,

$$ c \mid \delta \Longrightarrow kc \mid k \delta \Longrightarrow \Delta \mid k \delta \qquad (1) $$

Par ailleurs,

$$ \begin{cases} \delta \mid a \Longrightarrow k\delta \mid ka \\ \delta \mid a \Longrightarrow k\delta \mid kb \end{cases}\Longrightarrow k\delta \mid \Delta \qquad (2) $$

Les assertions $(1)$ et $(2)$ montrent que :

$$ \begin{cases} \Delta \mid k \delta \qquad (1) \\ k\delta \mid \Delta \qquad (2) \end{cases}\Longrightarrow \Delta = k\delta $$

Et finalement,

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b, \enspace \forall k \in \mathbb{Z},$$

$$ PGCD(ka, kb) = k.PGCD(a, b) $$

Lien entre PGCD et PPCM

Soit la décomposition de $a $ et de $b $ en facteurs premiers suivante :

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \exists! r \in \mathbb{N}^*, \enspace \exists! (p_1 < p_2 < ... < p_r) \in \mathbb{P}^r, \enspace \exists! (\alpha_1, \alpha_2, ..., \alpha_r) \in (\mathbb{N}^*)^r, \enspace \exists! (\beta_1, \beta_2, ..., \beta_r) \in (\mathbb{N}^*)^r, $$

$$ \begin{cases} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_r^{\beta_r} \end{cases} $$

On a vu plus haut que le $PGCD(a,b)$ peut s'écrire :

$$ PGCD(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_2^{min\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{min \{ \alpha_r, \beta_r\}} $$

Par ailleurs, le $PPCM(a,b)$ lui, peut s'écrire :

$$ PPCM(a, b) = p_1^{max \{ \alpha_1, \beta_1\}} \times p_2^{max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{max \{ \alpha_r, \beta_r\}} $$

En effectuant le produit des deux :

$$ PGCD(a, b) \times PPCM(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_1^{max \{ \alpha_1, \beta_1\}} \times p_2^{min \{ \alpha_2, \beta_2\}} \times p_2^{max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} \times p_r^{max \{ \alpha_r, \beta_r\}} $$

$$ PGCD(a, b) \times PPCM(a, b) = p_1^{min \{ \alpha_1, \beta_1\} + max \{ \alpha_1, \beta_1\}} \times p_2^{min \{ \alpha_2, \beta_2\} + max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{min \{ \alpha_r, \beta_r\} + max \{ \alpha_r, \beta_r\}} $$

$$ PGCD(a, b) \times PPCM(a, b) = p_1^{\alpha_1 + \beta_1} \times p_2^{\alpha_2+ \beta_2} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{ \alpha_r + \beta_r} $$

$$ PGCD(a, b) \times PPCM(a, b) = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta_2} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_r^{ \alpha_r}p_r^{ \beta_r} $$

Or, ce produit équivaut à $(ab)$ :

$$ ab = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta_2} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{ \alpha_r}p_r^{ \beta_r} $$

Soit finalement,

$$ \forall (a, b) \in \hspace{0.04em}\mathbb{N}^2, \enspace a > b,$$

$$ PGCD(a, b) \times PPCM(a, b) = ab $$

Les propriétés du PGCD de deux entiers naturels

Égalité entre les PGCD successifs de l'algorithme d'Euclide

Décomposition en facteurs premiers

Généralisation par indépendance des facteurs

Identité de Bézout

si \( b \) divise \( a \)

si \( b \) ne divise pas \( a \)

si \( R_0 \) divise \( b \)

si \( R_0 \) ne divise pas \( b \)

si \( R_1 \) divise \( R_0 \)

- si \( R_1 \) ne divise pas \( R_0 \)

Décomposition de deux nombres en lien avec leur PGCD

Égalité entre les diviseurs de a et de b et les diviseurs de leur PGCD

Sens direct : Si \( d \) divise \( a \) et \( b \), alors \( d \) divise \( \delta \)

Sens réciproque : Si \( d \) divise \( \delta \), alors \( d \) divise \( a \) et \( b \)

Conclusion

Linéarité

Lien entre PGCD et PPCM

Récapitulatif des propriétés du PGCD