Trouver des contenus d'apprentissage
Fonctionnalités
Découvrir
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 ?
Achieve better grades quicker with Premium
Geld-zurück-Garantie, wenn du durch die Prüfung fällst
Review generated flashcards
Commence à apprendre ou crée tes propres flashcards d'IA
Équipe enseignants Plus Grand Diviseur Commun
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.
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, \(\text{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 \( \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.
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 \(\text{GCD}(-36, 16) = 2\).
Qu'est-ce qui est vrai à propos du PGCD ?
Pour les entiers \(a, b\) et \(c\), le GCD a les propriétés suivantes :
Propriété d'identité : \(\text{GCD} (a,0)=|a|\).
La propriété de commutativité : \(\text{GCD} (a,b)=\text{GCD} (b,a)\).
La propriété associative : \(\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{GCD} (a, b),c)\).
La propriété distributive : \(\text{GCD} (ab, ac) =a \text{GCD} (b,c)\).
Voyons un exemple qui applique ces propriétés.
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]
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.
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 :
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) :
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.
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]
Prends deux entiers positifs, \(a\N) et \N(b\N) tels que \N(a>b\N). Pour calculer \(\text{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
\[\text{GCD} (a,b)=\text{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
\[\text{GCD} (b,r_1)=\text{GCD} (r_1,r_2).\]
Étape 3 : Puisque \(r_1>r_2\), tu sais que \(r_1=r_2q_3+r_3\). Cela signifie que
\[\text{GCD} (r_1, r_2)=\text{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.
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
\[\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).
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 \(\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\).
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 :
\[\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{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 \(\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]
Qu'en est-il du 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.
Propriété d'identité : \(\text{GCD} (a,0)=|a|\).
La propriété de commutativité : \(\text{GCD} (a,b)=\text{GCD} (b,a)\).
La propriété associative : \(\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{GCD} (a, b),c)\).
La propriété distributive : \(\text{GCD} (ab, ac) =a \text{GCD} (b,c)\).
Inscris-toi gratuitement pour accéder à toutes nos fiches.
At StudySmarter, we have created a learning platform that serves millions of students. Meet the people who work hard to deliver fact based content as well as making sure it is verified.
Lily Hulatt is a Digital Content Specialist with over three years of experience in content strategy and curriculum design. She gained her PhD in English Literature from Durham University in 2022, taught in Durham University’s English Studies Department, and has contributed to a number of publications. Lily specialises in English Literature, English Language, History, and Philosophy.
Get to know Lily
Gabriel Freitas is an AI Engineer with a solid experience in software development, machine learning algorithms, and generative AI, including large language models’ (LLMs) applications. Graduated in Electrical Engineering at the University of São Paulo, he is currently pursuing an MSc in Computer Engineering at the University of Campinas, specializing in machine learning topics. Gabriel has a strong background in software engineering and has worked on projects involving computer vision, embedded AI, and LLM applications.
Get to know Gabriel
Resumes 
Flashcards 
StudySmarter IA 
Notes de cours 
Planning de révision 
Dossiers 
Examens 
Magazine 
Faire carrière 
App mobile