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 :

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

$$ \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 (\text{avec} \enspace a' \wedge b' = 1)$$

Démonstrations

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

Soient $(a, b) \in \hspace{0.04em}\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.04em}\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.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 :

$$ \forall n \in \mathbb{N}, \enspace \forall p_n \in \mathbb{P}, \enspace \exists (\alpha_n, \beta_n) \in \hspace{0.04em}\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.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 / 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, \enspace \text{avec} \enspace \Biggl \{ \begin{gather*} u = 0\\ v = 1 \end{gather*} $$

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 $$

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, \enspace avec \enspace \Biggl \{ \begin{gather*} u = 1\\ v = -q_0 \end{gather*} $$

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 $$

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 \enspace avec \enspace \Biggl \{ \begin{gather*} u = -q_1 \\ v = -1 + q_0 q_1 \end{gather*} $$

- 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 / 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.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 \Biggl \{ \begin{gather*} a = \delta a' \\ b = \delta b'\end{gather*} \enspace \enspace (\text{avec} \enspace a' \wedge b' = 1)$$

Soit finalement,

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,

$$ \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.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 :

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

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

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