Le plus grand commun diviseur (GCF) est le plus grand nombre par lequel deux nombres ou plus peuvent être divisés. Ceci, sans laisser de résidus.
C'est-à-dire que le plus grand diviseur commun ou GCF est le chiffre le plus élevé par lequel un ensemble de nombres peut être divisé, ce qui donne un nombre entier.
Un diviseur peut être formellement défini comme ce nombre qui est contenu dans un autre exactement un nombre n de fois.
Il est à noter que les nombres sur lesquels le GCF est calculé doivent être non nuls.
Pour mieux l'expliquer, regardons un exemple. Supposons que nous ayons 35 et 15. Ainsi, nous observons quels sont les diviseurs de chacun :
- Diviseurs de 35 → 35,7,5,1
- Diviseurs de 15 → 15,5,3,1
Par conséquent, le plus grand facteur commun de 35 et 15 est 5.
Il convient de mentionner que si les diviseurs communs de deux nombres ne sont que 1 et -1, ils sont appelés « premiers l'un par rapport à l'autre ».
Méthodes pour calculer le plus grand diviseur commun
On peut distinguer les trois méthodes suivantes pour calculer le plus grand commun diviseur :
- Décomposition en facteurs premiers : Les nombres sont décomposés en nombres premiers. Ensuite, pour calculer le GCF, nous prenons les nombres communs élevés à la puissance la plus faible. Par exemple, supposons que nous ayons 216 et 156 :
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Par conséquent, le plus grand diviseur commun entre les deux nombres serait : (2 2) * 3 = 12
Supposons maintenant que nous ayons trois éléments : 315, 441 et 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Ensuite, après les avoir désagrégés, en prenant chaque diviseur avec sa puissance la plus faible, le résultat serait :
GCF = (3 2) * 7 = 63
- L'algorithme d'Euclide: lors de la division à Entrez b, un quotient est obtenu c et un r. Ainsi, le plus grand diviseur commun de à Oui b est le même que b Oui r. Ceci, étant donné ce qui suit : a = bc + r. Pour mieux le comprendre, appliquons cette méthode à l'exemple montré précédemment avec 216 et 156.
216/156 = 1 avec le reste de 60
maintenant nous divisons 156/60 = 2 avec le reste 36
On divise à nouveau 60/36 = 1 avec reste 24
Encore une fois on divise 36/24 = 1 avec le reste 12
Et enfin on divise 24/12 = 2 avec reste 0
Par conséquent, le plus grand diviseur commun est 12. Comme nous pouvons le voir, nous devons diviser jusqu'à ce que le reste soit 0 et le dernier diviseur sera le GCF.
- Basé sur le plus petit commun multiple: Les nombres sont multipliés et le résultat divisé par leur plus petit multiple commun (LCM).
Il faut se rappeler que le plus petit commun multiple (LCM) est le plus petit chiffre qui satisfait à la condition d'être un multiple de tous les éléments d'un ensemble de nombres.
Autrement dit, en reprenant le même exemple, nous pouvons décomposer comme suit :
216 = (3 3) * (2 3) et 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Le multiple le moins commun serait : (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Donc : PGCD = 216 * 156 / 2,808 = 12
Il est à noter que cette méthode ne fonctionne que pour deux nombres.