Pour tout \( (a, b) \in \hspace{0.05em}\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 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\}} $$
$$ \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)$$
$$ \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) $$
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b,$$
$$ PGCD(a, b) \times PPCM(a, b) = ab $$
Récapitulatif des propriétés du \(PGCD(a, b)\)
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) \).
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) $$
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\}} $$
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 \).
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*} $$
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 $$
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*} $$
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 $$
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*} $$
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.
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)$$
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) $$
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 $$
Récapitulatif des propriétés du \(PGCD(a, b)\)
Retour en haut de page
