Plus Grand Diviseur Commun

Qu'est-ce que \( \text{GCD}(4, 12)\) ?

Réponse :

Le PGCD de \N(4\N) et \N(12\N) est \N(4\N), puisque \N(4\N) est le plus grand nombre naturel qui divise \N(4\N) et \N(12\N) en même temps.

Qu'est-ce que \N(\text{GCD}(-36, 16)\N) ?

Réponse :

Tu sais que les diviseurs de \(-36\) sont \(\pm 36, \pm 18, \pm 9, \pm 3, \pm 2, \pm 1\). Les diviseurs de \N(16\N) sont \N(16, 8, 4, 2, 1\N). N'oublie pas que lorsque tu choisis le PGCD, tu prends toujours le plus grand nombre naturel qui divise les deux, de sorte que le PGCD est toujours un nombre positif. En regardant les listes de diviseurs, tu peux donc voir que \(\text{GCD}(-36, 16) = 2\).

Trouve ce qui suit :

(a) \(\text{GCD} (-4,0) \)

(b) \N-(\N-text{GCD} (10, 24, 35) \N-(\N-text{GCD} (10, 24, 35) \N)

(c) \N-( \text{GCD} ( 24, 36) \N )

Réponse:

(a) En utilisant la propriété de l'identité et la propriété de la commutativité,

\[\begin{align} \text{GCD} (-4,0)&=\text{GCD} (0,-4)\\\N- &=|-4| \N- &=4 .\Nend{align}\N]

(b) Utilisons la propriété d'association, qui nous dit que

\[ \begin{align} \text{GCD} (10, 24, 35) &= \text{GCD} (10, \text{GCD} (24, 35)) \\\\N &= \text{GCD} (\text{GCD} (10, 24),35).\Nend{align} \]

En commençant par celui qui semble le plus facile, \( \text{GCD} (24, 35) = 1\). Donc

\[ \begin{align} \text{GCD} (10, 24, 35) &= \text{GCD} (10, \text{GCD} (24, 35)) \\N &= \text{GCD} (1,24).\N &= 24. \Nend{align} \]

(c) C'est un bon endroit pour utiliser la propriété distributive, puisque \(24\) et \(36\) sont divisibles par \(2\). Cela signifie que

\[ \begin{align} \text{GCD} (24, 36) &= \text{GCD} (2\cdot 12, 2\cdot 18) \\\N &= 2\cdot \text{GCD} (12, 18). \Nend{align} \]

Tu sais que \N(12\N) et \N(18\N) sont divisibles par \N(2\N), tu peux donc utiliser à nouveau la propriété distributive pour obtenir

\N- \N[ \N- \N- \N- \N{align}} \N-text{GCD} (24, 36) &= 2\Ncdot \N-text{GCD} (12, 18) \N-text{GCD} (2\Ncdot 6, 2\Ncdot 9)\N-text{GCD} (6, 9) &= 2\Ncdot 2 \Ncdot \N-text{GCD} (6, 9) \N-text{GCD} (6, 9) &= 4\Ncdot \N-text{GCD} (6, 9) .\N-end{align} \]

Mais maintenant, \N(3\N) divise à la fois \N(6\N) et \N(9\N), donc tu peux utiliser la propriété distributive une fois de plus pour obtenir

\[ \begin{align} \N-text{GCD} (24, 36) &= 4 \N-text{GCD} (6, 9) \N-text{GCD} (3\cdot 2, 3\cdot 3)\N-text{GCD} (3\cdot 2, 3\cdot 3)\N-text{GCD} (2, 3) \N-text{GCD} (2, 3) \N-text{GCD} (2, 3) &= 12\N-text{GCD} (2, 3) .\N-end{align} \]

Puisque \(\text{GCD} (2, 3) = 1 \) tu peux maintenant dire que

\[ \N-text{GCD} (24, 36) = 12.\N-text{GCD} (24, 36) = 12.\N]

Supposons que nous voulions trouver le PGCD de \N(12, 46\) et \N(78\).

Réponse :

Par inspection, tu peux dresser la liste de tous les facteurs de ces trois nombres :

• Les facteurs de \N(12\N) sont \N(1, 2, 3, 4, 6, 12\N).
• Les facteurs de \N(46\N) sont \N(1, 2, 23, 46\N).
• Les facteurs de \N(78\N) sont \N(1, 2, 3, 6, 13, 26, 39, 78\N).

Puisque le plus grand nombre qui apparaît dans les trois listes est \N(2\N), tu devrais écrire \N(\text{GCD} (12,46,78)=2\N).

Trouve le plus grand diviseur commun de \(15\) et \(36\).

Réponse :

Tu peux commencer par écrire tous les diviseurs de \N(15\N) et de \N(36\N) :

• Les diviseurs de \N(15\N) sont \N(1, 3, 5, 15.\N)
• Les diviseurs de \N(36\N) sont \N(1, 2, 3, 4, 6, 9, 12, 18,36.\N)

Tu peux maintenant voir qu'il y a deux diviseurs communs à \N(15\N) et \N(36\N) : \N(1\N) et \N(3\N).

Tu choisis celui qui est le plus grand, donc \N(3\N) est le plus grand diviseur commun de \N(15\N) et \N(36\N).

En prenant les entiers \(44\) et \(17\) et en effectuant une division longue, on obtient

$$\begin{array}{r}2\phantom{)} \\17{\overline{\smash{\big)}\,44\phantom{)}}\ \underline{-~\phantom{(}0\phantom{-b)}\\ 44\phantom{)}\\ \underline{-~\phantom{()}34}\ 10\phantom{)} \end{array}$$.

Par conséquent, 44 divisé par 17 donne le quotient 2 avec le reste 10.

Soit donc \(a=44\) et \(b=17\), puis la substitution dans la formule donne

\N- [\N- a&=qb+r \N- 44&=2\Ncdot17+10. \N- end{align}\N]

Utilise l'algorithme d'Euclide pour trouver le plus grand diviseur commun de \(44\) et \(17\).

Réponse :

Étape 1 : Puisque \(44>17\), divise \(44\) par \(17\) de sorte que \(44=17\cdot 2+10\) où \(10\) est le reste lorsque \(44\) est divisé par \(17\). Alors

\[\text{GCD} (44,17)=\text{GCD} (17,10) .\]

Étape 2 : Divise maintenant \N(17\N) par \N(10\N) de sorte que \N(17=1 \Ncdot 10+7\N). Donc

\[\text{GCD} (17,10)=\text{GCD} (10,7).\]

Étape 3 : Maintenant \(10=1\cdot 7+3\), donc

\[\text{GCD} (10,7)=\text{GCD} (7,3) .\]

Étape 4 : Ici, \N(7=2\cdot 3+1\), donc

\[\text{GCD} (7, 3)=\text{GCD} (3, 1).\]

Étape 5 : dans cette étape, \( 3=1\cdot 3\) n'a pas de reste. Par conséquent, \N(\text{GCD} (44,17)=1\N).

Trouve le PGCD de \(12\) et de \(30\) en utilisant l'algorithme d'Euclide.

Réponse :

Puisque \(30 > 12\), \(a=30\) et \(b=12\) dans l'algorithme euclidien.

Étape 1 : Tu dois maintenant écrire \N(a\N) sous la forme \N(a=bq+r\N), ce qui te donne \N(30=(12\Ncdot 2)+6\N).

Tu sais que \(\text{GCD} (a, b) =\text{GCD} (b, r)\), donc

\[\text{GCD} (30, 12) = \text{GCD} (12, 6).\]

Étape 2 : Maintenant, laisse \N(b=12\N) et \N(r_1=6\N) et exécute à nouveau le même processus. Cela signifie que \(12=(6\cdot 2)+0\).

Maintenant, \N(r_1=6\N) et \N(r_2=0\N), donc

\[\text{GCD} (r_1,r_2)=\text{GCD} (6,0)=6 .\]

Étape 4 : attends, l'algorithme se termine dès que tu obtiens un reste de \(0\), ce qui est déjà le cas ! Cela signifie que tu peux sauter l'étape 4.

Étape 5 : Maintenant, tu sais que

\[ \begin{align} \text{GCD} (6,0) &=\text{GCD} (12,6) \\\N- &=\text{GCD} (30,12) \N- &=6 . \N- [end{align}\N]

Par conséquent, le PGCD de \(30\) et \(12\) est \(6\).

Trouve le plus grand diviseur commun de \(32\N), \N(254\N) et \N(372\N).

Réponse :

Tu dois d'abord utiliser l'algorithme d'Euclide pour trouver \N(\text{GCD} (32,254) = 2\N). Ensuite, tu peux utiliser à nouveau l'algorithme euclidien pour voir que \(\text{GCD} (2,372) =2\).

Donc, en vertu de la propriété d'association,

\N[ \Ncommencer{aligner} \text{GCD} (32, 254, 372) &=\text{GCD} (\text{GCD} (32,254), 372) \\N- & =\N-{GCD} (2,372)\N- &=2 . \N- [end{align}\N]