PGCD de deux entiers
Le cadre
Pour deux entiers strictement positifs n et m, la liste de leurs diviseurs est finie et comporte 1 en commun.
Le Plus Grand Commun Diviseur (PGCD) de n et m est donc bien défini.
PGCD de 12 et 16
- Les diviseurs de 12 sont : \(1, 2, 3, \mathbf{4}, 6, 12\)
- Les diviseurs de 16 sont : \(1, 2, \mathbf{4}, 8, 16\)
Le plus grand diviseur commun est 4.
PGCD de n et zéro
-
Les diviseurs de zéro sont tous les entiers, en effet zéro est un multiple de tout entier. (\(0×k = 0\) pour tout \(k\in\mathbb N\))
-
Les diviseurs communs à
net zéro, sont donc tous les diviseurs den.
Si n > 0, le plus grand diviseur est \(n\), ainsi pgcd(n, 0) est égal à n.
PGCD de zéro et zéro
Les diviseurs de zéro sont tous les entiers, et donc les diviseurs communs à zéro et zéro sont également tous les entiers, sans limite, et sans plus grand.
On étend pourtant la définition avec pgcd(0, 0) égal à 0.
Cela permet aux formules suivantes de rester également valables dans ce cas.
Ce n'est qu'une convention très utile !
Cas général, simplement
Pour calculer le PGCD, on peut utiliser une propriété mathématique de la fonction pgcd pour deux entiers positifs n et m
- Si
m = 0, alorspgcd(n, m)est égal àn - Sinon,
pgcd(n, m)est égal au PGCD entremet le reste de la division denparm.
Exercice
Coder une fonction récursive pgcd qui prend en paramètre deux entiers garantis positifs.
le module math est désactivé pour cet exercice.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)