French flag English flag
Index des cours

L'algorithme d'Euclide

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

L'algorithme d'Euclide nous dit que :

  1. Si \( b \) divise \( a \)
  2. $$ b / a \Longrightarrow PGCD(a, b) = b $$

  3. Si \( b\) ne divise pas \( a\)
  4. Le \( PGCD(a, b) \) est le dernier reste non nul \( R_n \) de la division euclidienne de \( a \) par \( b \) tel que :

    $$ a = \textcolor{#A65757}{b} q_0 + \textcolor{#446e4f}{R_0} $$

    Tant que le reste ne divise pas le diviseur de la division précédente, on continue l'algorithme.

    On redécompose alors à chaque étape le nouvel élément :

    $$ b = \textcolor{#A65757}{R_0} q_1 + \textcolor{#446e4f}{R_1} \ \Longrightarrow \ R_0 = \textcolor{#A65757}{R_1} q_2 + \textcolor{#446e4f}{R_2} \ \Longrightarrow \ R_k = \textcolor{#A65757}{R_{k + 1}} q_{k + 2} + \textcolor{#446e4f}{R_{k + 2}} $$

    $$ jusque \ \Longrightarrow R_{n - 3} = q_{n -1 }\textcolor{#A65757}{R_{n - 2}} + \textcolor{#446e4f}{R_{n -1}} $$

    Tant que le reste \( R_{n - 1} \) ne divise toujours pas \( R_{n - 2} \), le reste \( R_{n - 2} \) peut s'écrire :

    $$ R_{n - 2} = q_{n}\textcolor{#A65757}{R_{n - 1}} + \textcolor{#446e4f}{R_{n}} $$

    Jusqu'au moment où enfin \( R_n \) divise \( R_{n - 1} \), alors \( R_{n - 1} \) s'écrira :

    $$ R_{n - 1} = q_{n + 1}\textcolor{#A65757}{R_{n}} $$

    À ce moment, par remontée de l'algorithme en injectant tour à tour les valeurs précédentes jusque \( a \) et \( b \), on se rendra compte que l'on pourra toujours factoriser par \(R_{n} \). Et alors :

    $$ PGCD(a, b) = R_{n} $$


    \( \forall n \in \mathbb{N}\), \(\forall k \in [\![0, n ]\!] \), tant que le reste \(R_{k} \) ne divise pas le reste \(R_{k -1 } \) :

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


Démonstration

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

  1. Si \( b \) divise \( a \)
  2. Alors, \( a \) s'écrit :

    $$ a = bq_0 \qquad (a) $$

    Et à ce moment-là, comme \( b /a \) et \( b/b \), alors \( PGCD(a, b) = b\).

    $$ b / a \Longrightarrow PGCD(a, b) = b $$

  3. Si \( b \) ne divise pas \( a \)
  4. Dans ce cas, \( a \) peut s'écrire sous la forme :

    $$ a = \textcolor{#A65757}{b}q_0 + \textcolor{#446e4f}{R_0} \qquad (a-R_0) $$

    1. si \( R_0 \) divise \( b \)
    2. Alors \( b \) s'écrit :

      $$ b = q_1R_0 \qquad (b) $$

      On peut remonter l'algorithme et injecter \( (b) \) dans \( (a-R_0) \) :

      $$ a = bq_0 + R_0 = q_1R_0q_0 + R_0 = R_0 \underbrace{(q_1 q_0 + 1)} _\text{ \( Q_{a} \in \mathbb{N} \)} $$

      Soit,

      $$ a = Q_{a}R_0 \qquad (a') $$

      On a alors,

      $$ \Biggl \{ \begin{align*} a = Q_{a}R_0 \qquad (a') \\ b = q_1R_0 \qquad (b) \end{align*} $$

      Et à ce moment-là, comme \( R_0 /a \), \( R_0/b \) et \( R_0/R_0 \), alors :

      $$ PGCD(a, b) =PGCD(b, R_0) = R_0 $$

    3. si \( R_0 \) ne divise pas \( b \)
    4. Dans ce cas, \( b \) peut s'écrire sous la forme :

      $$ b = \textcolor{#A65757}{R_0} q_1 + \textcolor{#446e4f}{R_1} \qquad (b-R_1) $$

      1. - si \( R_1 \) divise \( R_0 \)
      2. Alors \( R_0 \) s'écrit :

        $$ R_0 = q_2R_1 \qquad (R_0) $$

        On peut remonter l'algorithme et injecter \( (R_0) \) dans \( (b-R_1) \) :

        $$ b = R_0 q_1 + R_1 = q_2R_1 q_1 + R_1 = R_1 \underbrace{(q_2 q_1 + 1)} _\text{ \( Q_{b} \in \mathbb{N} \)} $$

        Soit,

        $$ b = Q_{b}R_1 \qquad (b') $$

        On remonte encore une fois en injectant cette fois la nouvelle valeur de \( (b') \) et de \( (R_0) \) dans \( (a-R_1) \) :

        $$a = bq_0 + R_0 = Q_{b}R_1q_0 + q_2R_1 = R_1 \underbrace{(Q_{b} q_0 + q_2)} _\text{ \( Q_{a} \in \mathbb{N} \)} $$

        $$a = Q_{a}R_1 \qquad (a') $$

        On a alors,

        $$ \Biggl \{ \begin{align*} a = Q_{a}R_1 \qquad (a') \\ b = Q_{b}R_1 \qquad (b') \end{align*} $$

        Et à ce moment-là, comme \( R_1 /a \), \( R_1/b \), \( R_1/R_0 \) et \( R_1/R_1 \), alors :

        $$ PGCD(a, b) =PGCD(b, R_0) =PGCD(R_0, R_1) = R_1 $$

      3. - si \( R_1 \) ne divise pas \( R_0 \)
      4. Dans ce cas, \( R_0 \) peut s'écrire sous la forme :

        $$ R_0 = \textcolor{#A65757}{R_1} q_2 + \textcolor{#446e4f}{R_2} \qquad (R_0 - R_2) $$

        On continue l'algorithme comme cela jusqu'à ce que \( R_n \) divise \( R_{n- 1} \) et à ce moment-là :

        $$ R_{n - 1} = q_{n + 1}\textcolor{#A65757}{R_n} $$

        Ainsi, par remontée on aura :

        $$ R_{n - 2} = q_{n} \textcolor{#A65757}{R_{n - 1}} + \textcolor{#446e4f}{R_n} $$

        $$ R_{n - 2} = q_{n}\textcolor{#A65757}{q_{n + 1}R_n} + \textcolor{#446e4f}{R_n} = R_n\underbrace{(q_{n}q_{n + 1} + 1)} _ \text{ \( Q_{n - 2} \in \mathbb{N} \) } $$

        $$ R_{n - 2} = R_nQ_{n - 2} $$

        Par suite, on a une réaction en chaîne jusqu'au début de l'algorithme :

        $$ \Biggl[ R_{n - 3} = R_nQ_{n - 3} \Biggr] \Longrightarrow ... \Longrightarrow \Biggl[ R_{n - k} = R_nQ_{n - k} \Biggr] \Longrightarrow ... \Longrightarrow \Biggl[ R_{2} = R_nQ_{2} \Biggr] $$

        $$ \Biggl[ R_{1} = R_nQ_{1}\Biggr] \Longrightarrow \Biggl[ R_{0} = R_nQ_{0} \Biggr] \Longrightarrow \Biggl[ b = R_nQ_{b}\Biggr] \Longrightarrow \Biggl[ a = R_nQ_{a}\Biggr] $$

        \( R_n \) sera alors le plus diviseur commun à tous ces nombres.


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



Et finalement,

\( \forall n \in \mathbb{N}\), \(\forall k \in [\![0, n ]\!] \), tant que le reste \(R_{k} \) ne divise pas le reste \(R_{k -1 } \) :

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

Ce reste \( R_n \) pourra lui-même se décomposer en différents facteurs, qui composeront l'ensemble des diviseurs de \( a \) et de \( b \) :

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


Exemples


  1. Calcul de \( PGCD(1365, 25) \)
  2. On a vu avec l'algorithme qu'il va falloir effectuer des divisions successives, afin de récupérer le dernier reste non nul de cette série de division.

    1. Calcul de \( 1365 / 25 \)

    2. Algorithme d'Euclide - première division

      \( 25 \) ne divise pas \( 1365 \), car cela ne tombe pas juste. On récupère d'abord sa partie entière.

      $$ \left \lfloor{\frac{1365}{25}} \right \rfloor = 54 \hspace{5em} (1ère \ division) $$

      Alors \( 1365 \) peut s'écrire :

      $$ 1365 = \textcolor{#A65757}{25} \times 54 + \textcolor{#446e4f}{R_0} $$

      Calculons le reste \( \textcolor{#446e4f}{R_0} \).

      $$ \textcolor{#446e4f}{R_0} = 1365 -\textcolor{#A65757}{25} \times 54 = \textcolor{#446e4f}{15} \hspace{5em} (R_0) $$

      Soit,

      $$ 1365 = \textcolor{#A65757}{25} \times 54 + \textcolor{#446e4f}{15} \qquad (a) $$

      $$ (a = \textcolor{#A65757}{b} q_0 + \textcolor{#446e4f}{R_0}) $$

    3. Calcul de \( 25 / 15 \)

    4. Algorithme d'Euclide - deuxième division

      \( 15 \) ne divise pas \( 25 \).

      $$ \left \lfloor{\frac{25}{15}} \right \rfloor = 1 \hspace{5em} (2ème \ division) $$

      Alors \( 25 \) peut s'écrire :

      $$ 25 = \textcolor{#A65757}{15} \times 1 + \textcolor{#446e4f}{10} \qquad (b) $$

      $$ (b = \textcolor{#A65757}{R_0} q_1 + \textcolor{#446e4f}{R_1}) $$

    5. Calcul de \( 15 / 10 \)

    6. Algorithme d'Euclide - troisième division

      \( 10 \) ne divise pas \( 15 \).

      $$ \left \lfloor{\frac{15}{10}} \right \rfloor = 1 \hspace{5em} (3ème \ division) $$

      Alors \( 15 \) peut s'écrire :

      $$ 15 = \textcolor{#A65757}{10} \times 1 + \textcolor{#446e4f}{5} \qquad (R_0) $$

      $$ (R_0 = \textcolor{#A65757}{R_1} q_2 + \textcolor{#446e4f}{R_2}) $$

    7. Calcul de \( 10 / 5 \)

    8. Algorithme d'Euclide - quatrième division

      Cette fois-ci, \( 5 \) divise \( 10 \). Le reste est nul.

      $$ \frac{10}{5} = 2 \hspace{5em} (4ème \ division) $$

      Alors \( 10 \) peut s'écrire :

      $$ 10 = \textcolor{#A65757}{5} \times 2 \qquad (R_1) $$

      $$ (R_1 = \textcolor{#A65757}{R_2} q_3) $$

      On a donc comme résultat final :

      $$ PGCD(1365, 25) = 5 $$

      $$ (PGCD(a, b) = R_2) $$

      Algorithme d'Euclide - divisions successives

  3. Remontée de l'algorithme

  4. On peut éventuellement remonter l'algorithme et trouver deux nombres qui conviennent à l'indetité de Bézout.

    Ce théorème nous dit que :

    $$ \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 (Bachet-Bézout)$$

    Pour cela, on va à chaque fois réinjecter les valeurs dans les résultats du calcul précédent.

    $$ \Biggl \{ \begin{gather*} \underline{10} \hspace{0.1em} = \textcolor{#A65757}{5} \times 2 \qquad (R_1) \\ 15 = \hspace{0.1em} \underline{\textcolor{#A65757}{10}} \hspace{0.1em} \times 1 + \textcolor{#446e4f}{5} \qquad (R_0) \end{gather*} \enspace \Longrightarrow \enspace 15 = \textcolor{#A65757}{(5 \times 2)} \times 1 + \textcolor{#446e4f}{5} \qquad (R_0') $$

    On isole la valeur du \( PGCD \) car c'est elle qu'on veut à la fin comme résultat.

    $$ 15 = \textcolor{#A65757}{10} \times 1 + \textcolor{#446e4f}{5} \qquad (R_0) \enspace \Longleftrightarrow \enspace \textcolor{#446e4f}{5} = 15 - \textcolor{#A65757}{10} \times 1 \qquad (R_2) $$

    Ensuite, on a :

    $$ 25 = \textcolor{#A65757}{15} \times 1 + \textcolor{#446e4f}{10} \qquad (b) \enspace \Longleftrightarrow \enspace \textcolor{#446e4f}{10} = 25 - \textcolor{#A65757}{15} \times 1 \qquad (R_1') $$

    Avec l'injection de \( (R_1') \) dans \( (R_2) \), on a :

    $$ \Biggl \{ \begin{gather*} \textcolor{#446e4f}{5} = 15 - \hspace{0.1em} \underline{ \textcolor{#A65757}{10} } \hspace{0.1em} \times 1 \qquad (R_2) \\ \hspace{0.1em} \underline{ \textcolor{#446e4f}{10} } \hspace{0.1em} = 25 - \textcolor{#A65757}{15} \times 1 \qquad (R_1') \end{gather*} \enspace \Longrightarrow \enspace \textcolor{#446e4f}{5} = 15 - ( 25 - \textcolor{#A65757}{15} \times 1 ) \times 1 \qquad (R_2') $$

    Encore, on a :

    $$ 1365 = \textcolor{#A65757}{25} \times 54 + \textcolor{#446e4f}{15} \qquad (a) \enspace \Longleftrightarrow \enspace \textcolor{#446e4f}{15} = 1365 - \textcolor{#A65757}{25} \times 54 \qquad (R_0'') $$

    Avec la double injection de \( (R_0'') \) dans \( (R_2') \), on a :

    $$ \Biggl \{ \begin{gather*} \hspace{0.1em} \underline{ \textcolor{#446e4f}{15} } \hspace{0.1em} = 1365 - \textcolor{#A65757}{25} \times 54 \qquad (R_0'') \\ \textcolor{#446e4f}{5} = \hspace{0.1em} \underline{ 15 } \hspace{0.1em} - ( 25 - \hspace{0.1em} \underline{ \textcolor{#A65757}{15} } \hspace{0.1em} \times 1 ) \times 1 \qquad (R_2') \end{gather*} \enspace \Longrightarrow \enspace \textcolor{#446e4f}{5} = 1365 - \textcolor{#A65757}{25} \times 54 - ( 25 - ( 1365 - \textcolor{#A65757}{25} \times 54 ) \times 1 ) \times 1 \qquad (R_2'') $$

    Soit,

    $$ \textcolor{#446e4f}{5} = 1365 - \textcolor{#A65757}{25} \times 54 - 25 + 1365 - \textcolor{#A65757}{25} \times 54 \qquad (R_2''') $$

    $$ \textcolor{#446e4f}{5} = 1365 \times 2 + \textcolor{#A65757}{25} \times (-54 - 54 -1) $$

    $$ \textcolor{#446e4f}{5} = 1365 \times 2 + \textcolor{#A65757}{25} \times (-109) $$

    On a bien :

    $$ 5 = 1365 \wedge 25 \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace 1365u + 25v = 5 $$

    $$ avec \ \Biggl \{ \begin{gather*} u = 2 \\ v = -109 \end{gather*} $$

Index des cours
Retour en haut de page