French flag English flag
Index des cours

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

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

  1. \( \delta = a \wedge b = PGCD(a, b) \);

  2. 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.

  3. \( \mathcal{D}(a, b)\) l'ensemble des diviseurs communs à \( a \) et à \( b \);

  4. \( \mathcal{D}(\delta)\) l'ensemble des diviseurs de \( PGCD(a, b) \).


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

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

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

L'ensemble des diviseurs communs à \( a \) et à \( b \) est 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) $$


Décomposition en facteurs premiers

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

Soit la décomposition de \(a \) et de \(b \) en facteurs premiers :

$$ \forall n \in \mathbb{N}, \enspace \forall p_n \in \mathbb{P}, \enspace \exists (\alpha_n, \beta_n) \in \hspace{0.05em}\mathbb{N}^2, \enspace \Biggl \{ \begin{gather*} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_n^{\beta_n} \end{gather*} $$

Alors,

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


Identité de Bézout

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

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


Décomposition de deux nombres en lien avec leur PGCD

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

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


Linéarité

$$ \forall (a, b) \in \hspace{0.05em}\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.05em}\mathbb{N}^2, \enspace a > b,$$

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


Démonstrations


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

Soient \((a, b) \in \hspace{0.05em}\mathbb{N}^2\) deux entiers naturels et \( \delta = PGCD(a, b) \).

Comme \( \delta \) est le plus grand diviseur commun à \( a \) et à \( b \), alors :

$$ \Biggl \{ \begin{gather*} \delta / a \Longrightarrow a = k\delta \\ \delta / b \Longrightarrow b = k'\delta \end {gather*} \qquad (1) $$

Supposons qu'il existe un diviseur \( d \ ( d \in \mathbb{N}) \) commun à \( a \) et à \( b \), tel que \( d < \delta \), et qui ne divise pas \( \delta \).

Alors, on aurait :

$$ \Biggl \{ \begin{gather*} d / a \Longrightarrow a = qd \\ d / b \Longrightarrow b = q'd \\ d \nmid \delta \Longrightarrow \delta = Qd + R \end {gather*} \qquad (2) $$

Par suite, les expressions \( (1) \) et \( (2) \) combinées donnent :

$$ \Biggl \{ \begin{gather*} a = k\delta = qd \Longrightarrow k ( Qd + R ) = qd \\ b = k'\delta = q'd \Longrightarrow k' ( Qd + R ) = q'd \end {gather*} $$

$$ \Biggl \{ \begin{gather*} a = kQd + k R = qd \\ b = k'Qd + k' R = q'd \end {gather*} \qquad (3) $$

La seule possibilité pour que \( (3) \) ait un sens serait que :

$$ \Biggl \{ \begin{gather*} k = d \\ k' = d \end {gather*} \enspace \Longrightarrow \enspace k = k' = d $$

Or, \( k \neq k' \) puisque \( a \neq b \) et \( \delta \) est unique, donc ce n'est pas possible.

On voit alors clairement que n'importe quel diviseur \( d \) commun à \( a \) et à \( b \) divise aussi leur \(PGCD\).


Soit que l'ensemble des diviseurs communs à \( a \) et à \( b \) est l'ensemble des diviseurs de \( PGCD(a, b) \).

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

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

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


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

Soient \((a, b) \in \hspace{0.05em}\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.05em}\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.05em}\mathbb{N}^2 \) deux entiers naturels avec \(a > b \).

Soit la décomposition de \(a \) et de \(b \) en facteurs premiers :

$$ \forall n \in \mathbb{N}, \enspace \forall p_n \in \mathbb{P}, \enspace \exists (\alpha_n, \beta_n) \in \hspace{0.05em}\mathbb{N}^2, \enspace \Biggl \{ \begin{gather*} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_n^{\beta_n} \end{gather*} $$

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

Le plus grand diviseur commun à deux nombres \( A = p^{\alpha} \) et \( B = p^{\beta} \) est :

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

Alors, en appliquant ce raisonnement à la décomposition primaire de \(a \) et à \( b \), on a:

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


Identité de Bézout

Soient \((a, b) \in \hspace{0.05em}\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 / a \) ou \( b \nmid a \).

  1. si \( b \) divise \( a \)
  2. 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, \enspace avec \enspace \Biggl \{ \begin{gather*} u = 0\\ v = 1 \end{gather*} $$

  3. si \( b \) ne divise pas \( a \)
  4. 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 \)
    2. 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, \enspace avec \enspace \Biggl \{ \begin{gather*} u = 1\\ v = -q_0 \end{gather*} $$

    3. - si \( R_0 \) ne divise pas \( b \)
    4. 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 \)
      2. 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 \enspace avec \enspace \Biggl \{ \begin{gather*} u = -q_1 \\ v = -1 + q_0 q_1 \end{gather*} $$

      3. - si \( R_1 \) ne divise pas \( R_0 \)
      4. 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.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (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.05em}\mathbb{Z}^2\) deux entiers relatifs.

Si \( \delta = a \wedge b\), alors \( \delta / a \) et \( \delta / b \), soit :

$$ \Biggl \{ \begin{gather*} a = \delta a' \\ b = \delta b' \end{gather*} $$

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 :

$$ \Biggl \{ \begin{gather*} a' = d a'' \\ b' = d b'' \end{gather*} $$

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.05em}\mathbb{N}^2, \enspace a > b, $$

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


Soit finalement,

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


Linéarité

Soient \((a, b) \in \hspace{0.05em}\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,

$$ \Biggl \{ \begin{gather*} k / ka \\ k / kb \end{gather*} \Longrightarrow k/\Delta $$

Si \( k/\Delta \), cela signifie aussi que :

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

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

$$ \Biggl \{ \begin{gather*} \Delta / ka \\ \Delta / kb \end{gather*} $$

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

$$ \Biggl \{ \begin{gather*} kc / ka \Longrightarrow c / a \\ kc / kb \Longrightarrow c / b \end{gather*} $$

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

$$ \Biggl \{ \begin{gather*} c / a \\ c / b \end{gather*} \Longrightarrow c/\delta $$

Et enfin,

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

Par ailleurs,

$$ \Biggl \{ \begin{gather*} \delta / a \Longrightarrow k\delta / ka \\ \delta / a \Longrightarrow k\delta / kb \end{gather*} \Longrightarrow k\delta/\Delta \qquad (2) $$

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

$$ \Biggl \{ \begin{gather*} \Delta/k \delta \qquad (1) \\ k\delta/\Delta \qquad (2) \end{gather*} \Longrightarrow \Delta = k\delta $$

Et finalement,

$$ \forall (a, b) \in \hspace{0.05em}\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 :

$$ \forall n \in \mathbb{N}, \enspace \forall p_n \in \mathbb{P}, \enspace \exists (\alpha_n, \beta_n) \in \hspace{0.05em}\mathbb{N}^2, \enspace \Biggl \{ \begin{gather*} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_n^{\beta_n} \end{gather*} $$

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 \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} $$

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 \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{max \{ \alpha_n, \beta_n\}} $$

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 \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} \times p_n^{max \{ \alpha_n, \beta_n\}} $$

$$ 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 \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\} + max \{ \alpha_n, \beta_n\}} $$

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

$$ PGCD(a, b) \times PPCM(a, b) = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{ \alpha_n}p_n^{ \beta} $$

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

$$ ab = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{ \alpha_n}p_n^{ \beta} $$


Soit finalement,

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

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

Index des cours
Retour en haut de page