Plus Grand Diviseur Commun

Suppose que tu aies deux longueurs de corde. L'une d'entre elles mesure 1,5 cm et l'autre 1,5 cm. Tu veux couper les deux morceaux en bandes de même longueur, aussi longues que possible. Comment dois-tu couper les morceaux ?

C'est parti

Fact Checked Content
Last Updated: 01.01.1970
reading time:12 min

Content creation process designed by
Content cross-checked by
Content quality checked by

Tu peux utiliser le concept du plus grand diviseur commun pour résoudre ce problème parce que tu divises les longueurs de corde en plus petits morceaux (facteurs) de \(48\N et \N(32\N), et tu cherches la plus grande longueur possible qui est commune aux deux morceaux d'origine. Ainsi, puisque le plus grand diviseur commun à \N(48\N) et \N(32\N) est \N(1\N), tu devrais couper chaque morceau pour qu'il fasse \N(12\N) pouces de long.

Ici, tu utilises le concept du plus grand commun diviseur pour diviser quelque chose en sections plus petites. Il existe de nombreuses autres applications du plus grand diviseur commun. Cet article explique ce qu'est le plus grand diviseur commun et présente deux méthodes différentes pour le trouver.

Signification du plus grand diviseur commun

Qu'est-ce que le plus grand diviseur commun ?

Leplus grand diviseur commun d'un groupe d'entiers, souvent abrégé en GCD, est défini comme le plus grand nombre naturel possible qui divise les nombres donnés avec zéro comme reste.

Pour couvrir le cas où les deux entiers sont nuls, $GCD (0, 0)$ est défini comme $0$ .

Le plus grand diviseur commun a de nombreuses applications pratiques, allant de la simplification des fractions et de la théorie des nombres aux algorithmes de cryptage.

Le plus grand diviseur commun (GCD) est également appelé le plus grand facteur commun (GCF) ou le plus grand facteur commun (HCF).

Prenons un exemple rapide.

Qu'est-ce que $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.

Encore un petit exemple.

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 $GCD (- 36, 16) = 2$ .

Qu'est-ce qui est vrai à propos du PGCD ?

Règles du plus grand diviseur commun

Pour les entiers $a, b$ et $c$ , le GCD a les propriétés suivantes :

Propriété d'identité : $GCD (a, 0) = | a |$ .
La propriété de commutativité : $GCD (a, b) = GCD (b, a)$ .
La propriété associative : $GCD (a, GCD (b, c)) = GCD (GCD (a, b), c)$ .
La propriété distributive : $GCD (a b, a c) = a GCD (b, c)$ .

Voyons un exemple qui applique ces propriétés.

Trouve ce qui suit :

(a) $GCD (- 4, 0)$

(b) \N-(\N-text{GCD} (10, 24, 35) \N-(\N-text{GCD} (10, 24, 35) \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

$Missing \end{align}$

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

$Missing \end{align}$

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

$Missing \end{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

$Missing \end{align}$

Puisque $GCD (2, 3) = 1$ tu peux maintenant dire que

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

Remarque qu'avant de trouver le PGCD, tu dois savoir quels sont les diviseurs (ou facteurs) des nombres, et en particulier quels sont leurs diviseurs communs. Rappelle-toi qu'un facteur d'un nombre \N(a\N) est un nombre \N(b\N) qui se divise en \N(a\N) sans reste.

Il existe deux façons principales de trouver le plus grand diviseur commun (PGCD) :

trouver tous les diviseurs communs (également appelé la méthode des facteurs communs) ; et
en utilisant l'algorithme d'Euclide.

La méthode du facteur commun

Pour cette méthode, tu utilises l'inspection pour écrire tous les diviseurs ou facteurs des nombres donnés, et tu choisis le plus grand. Ce sera ton plus grand diviseur commun. La méthode est plus facile à comprendre à l'aide d'un exemple.

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

Prenons un autre exemple.

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

Maintenant, pour trouver le plus grand diviseur commun pour des nombres plus grands, la méthode des diviseurs communs va devenir très longue et fastidieuse. C'est pourquoi tu utilises l'algorithme du plus grand diviseur commun, également connu sous le nom d'algorithme d'Euclide.

Encuentra materiales de estudio relevantes y prepárate para el día del examen

Inscris-toi gratuitement

Algorithme du plus grand diviseur commun

L'algorithme d'Euclide est un processus informatique qui permet de calculer le plus grand diviseur commun de deux nombres entiers positifs. Il utilise les restes pour trouver le plus grand diviseur commun entre les deux nombres.

Examinons d'abord le processus de la division longue. Prends deux entiers positifs, $a$ et $b$ tels que $a > b$ . La division euclidienneest un processus qui permet d'écrire \(a\N) et \N(b\N) sous la forme suivante

\N-[a=qb+r\N]

où $q$ est un entier positif appelé le quotient, et $0 \leq r < b$ est appelé le reste .

Prenons un exemple rapide de division longue.

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]

Étapes de l'algorithme d'Euclide

Prends deux entiers positifs, \(a\N) et \N(b\N) tels que \N(a>b\N). Pour calculer $GCD (a, b)$ , les étapes de l'algorithme euclidien sont les suivantes :

Étape 1 : Diviser \N(a\N) par \N(b\N) de sorte que \N(a=bq_1+r_1\N) où \N(r_1\N) est le reste lorsque \N(b\N) est divisé par \N(a\N). Dans ce cas

$GCD (a, b) = GCD (b, r_{1}) .$

Étape 2 : Puisque \N-(b>r_1\N), divise \N-(b\N) par \N-(r_1\N) de sorte que \N-(b=r_1q_2+r_2\N). Alors

$GCD (b, r_{1}) = GCD (r_{1}, r_{2}) .$

Étape 3 : Puisque $r_{1} > r_{2}$ , tu sais que $r_{1} = r_{2} q_{3} + r_{3}$ . Cela signifie que

$GCD (r_{1}, r_{2}) = GCD (r_{2}, r_{3}) .$

Étape 4 : Répète cette opération pour les autres jusqu'à ce que \N(r_k=0\N).

Étape 5 : Tu as alors

\N- [\N- Début{alignement} \text{GCD} (a,b)&=\text{GCD} (b,r_1) \\N- &=\text{GCD} (r_1, r_2) \N- &=\vdots \N- &=\text{GCD} (r_{k-1}, r_k) \N- &=\text{GCD} (r_{k-1},0) \N- &=r_{k-1} . \N- [end{align}\N]

Par conséquent, le PGCD est le dernier reste non nul de la division euclidienne. Bien sûr, la meilleure façon de comprendre cela est de prendre des exemples.

Mantente organizado y enfocado con tu lista de tareas inteligente

Inscris-toi gratuitement

Exemples de plus grand diviseur commun

Commençons par un exemple où tu sais que la réponse est censée être $1$ , afin que tu puisses voir que l'algorithme euclidien fonctionne.

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

$GCD (44, 17) = 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

$GCD (17, 10) = GCD (10, 7) .$

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

$GCD (10, 7) = GCD (7, 3) .$

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

$GCD (7, 3) = 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).

Voyons un autre exemple.

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 $GCD (a, b) = GCD (b, r)$ , donc

$GCD (30, 12) = 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

$GCD (r_{1}, r_{2}) = 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$ .

Le plus grand diviseur commun de trois nombres

Tu as déjà vu des exemples où tu as trouvé le PGCD de trois nombres ! Rappelle-toi qu'il s'agissait d'utiliser

la propriété associative :

$GCD (a, GCD (b, c)) = GCD (GCD (a, b), c) .$

Si tu le souhaites, tu peux utiliser l'algorithme d'Euclide pour trouver le plus grand diviseur commun de deux des nombres, puis l'utiliser à nouveau pour trouver le plus grand diviseur commun des trois nombres.

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

Qu'en est-il du plus grand diviseur commun des polynômes ?

Accède à des millions de fiches spécialement conçues pour t'aider à étudier

Inscris-toi gratuitement

Le plus grand diviseur commun des polynômes

Trouver le plus grand diviseur commun de deux polynômes est très similaire à trouver le plus grand diviseur commun de deux nombres. Cela nécessite la factorisation des polynômes et parfois la division longue des polynômes. Pour plus d'informations sur ces sujets, voir Opérations avec les polynômes et Factorisation des polynômes.

Le plus grand diviseur commun - Principaux enseignements

Le plus grand diviseur commun d'un ensemble de nombres est le plus grand nombre naturel par lequel tous les nombres de l'ensemble peuvent être divisés.
Le plus grand diviseur commun peut être trouvé en trouvant tous les facteurs de l'ensemble de nombres et en identifiant le plus grand facteur commun à tous les nombres de cet ensemble. Le PGCD peut également être déterminé à l'aide de l'algorithme d'Euclide. Cela signifie que pour deux entiers \(a\N) et \N(b\N), il faut écrire \N(a\N) sous la forme \N(a=bq+r\N) et répéter ce processus jusqu'à ce que \N(r=0\N). Les deux méthodes donnent la même réponse.
Le PGCD possède les propriétés suivantes :
- Propriété d'identité : $GCD (a, 0) = | a |$ .
- La propriété de commutativité : $GCD (a, b) = GCD (b, a)$ .
- La propriété associative : $GCD (a, GCD (b, c)) = GCD (GCD (a, b), c)$ .
- La propriété distributive : $GCD (a b, a c) = a GCD (b, c)$ .

S'inscrire avec un e-mail

Tu as déjà un compte ? Connecte-toi

Questions fréquemment posées en Plus Grand Diviseur Commun

Qu'est-ce que le Plus Grand Diviseur Commun (PGCD) ?

Le Plus Grand Diviseur Commun (PGCD) est le plus grand nombre qui divise deux nombres sans laisser de reste.

Comment calcule-t-on le PGCD de deux nombres ?

Pour calculer le PGCD de deux nombres, on peut utiliser l'algorithme d'Euclide, qui consiste à diviser les nombres jusqu'à obtenir un reste nul.

Pourquoi le PGCD est-il important en mathématiques ?

Le PGCD est important car il permet de simplifier les fractions et de résoudre des problèmes de divisibilité.

Le PGCD de deux nombres peut-il être plus grand que l'un d'eux ?

Non, le PGCD de deux nombres ne peut jamais être plus grand que le plus petit de ces nombres.

Sauvegarder l'explication

Découvre des matériels d'apprentissage avec l'application gratuite StudySmarter

Lance-toi dans tes études

À propos de StudySmarter

StudySmarter est une entreprise de technologie éducative mondialement reconnue, offrant une plateforme d'apprentissage holistique conçue pour les étudiants de tous âges et de tous niveaux éducatifs. Notre plateforme fournit un soutien à l'apprentissage pour une large gamme de sujets, y compris les STEM, les sciences sociales et les langues, et aide également les étudiants à réussir divers tests et examens dans le monde entier, tels que le GCSE, le A Level, le SAT, l'ACT, l'Abitur, et plus encore. Nous proposons une bibliothèque étendue de matériels d'apprentissage, y compris des flashcards interactives, des solutions de manuels scolaires complètes et des explications détaillées. La technologie de pointe et les outils que nous fournissons aident les étudiants à créer leurs propres matériels d'apprentissage. Le contenu de StudySmarter est non seulement vérifié par des experts, mais également régulièrement mis à jour pour garantir l'exactitude et la pertinence.