PGCD de deux entiers

Pour calculer le Plus Grand Commun Diviseur, on peut utiliser une propriété mathématique de la fonction pgcd pour deux entiers positifs n et m

PGCD de 12 et 16

• Les diviseurs de 12 sont : \(1, 2, 3, 4, 6, 12\)
• Les diviseurs de 16 sont : \(1, 2, 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 à n et zéro, sont donc tous les diviseurs de n.

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 de rester également valables dans ce cas.

Cas général

• Si m = 0, alors pgcd(n, m) est égal à n
• Sinon, pgcd(n, m) est égal au PGCD entre m et le reste de la division de n par m.

Exercice

Écrire une version récursive de la fonction pgcd

###

LancerTéléchargerTéléverser RechargerSauvegarder

def pgcd(n, m):bksl-nl """Renvoie le PGCD de n et mbksl-nl avec la convention pgcd(0, 0) égal à 0bksl-nl avec n et m positifsbksl-nl """bksl-nl ...bksl-nlbksl-nlassert pgcd(0, 0) == 0bksl-nlassert pgcd(12, 0) == 12bksl-nlassert pgcd(12, 16) == 4bksl-nlbksl-nl

Réponse

🐍 Script Python

def pgcd(n, m):
    """Renvoie le PGCD de n et m
    avec la convention pgcd(0, 0) égal à 0
    avec n et m positifs
    """
    if m == 0:
        return n
    else:
        return pgcd(m, n%m)

assert pgcd(0, 0) == 0
assert pgcd(12, 0) == 12
assert pgcd(12, 16) == 4