Algorithme d'Euclide étendu et programmes Python - Exercice 1

25 min
40
Méthode du tableau. Pour obtenir à la fois PGCD(a;b)\text{PGCD}\left(a;b\right) et un couple (u;v)\left(u;v\right) tel que au+bv=PGCD(a;b)au+bv=\text{PGCD}\left(a;b\right), on écrit des lignes L0\text{L}_{0}, L1\text{L}_{1}, L2\text{L}_{2}, … contenant un reste rr et deux coefficients uu et vv qui vérifient toujours r=au+bvr=au+bv :
  • L0\text{L}_{0} : r=ar=a, u=1u=1, v=0v=0 et L1\text{L}_{1} : r=br=b, u=0u=0, v=1v=1 ;
  • si qq est le quotient de la division euclidienne du reste de Lk−1\text{L}_{k-1} par le reste de Lk\text{L}_{k}, alors Lk+1=Lk−1−q×Lk\text{L}_{k+1}=\text{L}_{k-1}-q\times\text{L}_{k} (on soustrait colonne par colonne) ;
  • on s'arrête lorsque le reste est nul : le dernier reste non nul est le PGCD\text{PGCD}.
    • Question 1

    Appliquer la méthode avec a=252a=252 et b=198b=198.

    Correction
    Soient aa et bb deux entiers naturels non nuls et rr le reste de la division euclidienne de aa par bb.
  • PGCD(a;b)=PGCD(b;r)\text{PGCD}\left(a;b\right)=\text{PGCD}\left(b;r\right) et PGCD(a;0)=a\text{PGCD}\left(a;0\right)=a.
  • Le dernier reste non nul obtenu en appliquant l'algorithme d'Euclide est le PGCD\text{PGCD} de aa et bb.
    • On calcule d'abord les quotients successifs de l'algorithme d'Euclide :
    252=198×1+54\red{252}=\blue{198}\times\purple{1}+\pink{54}
    198=54×3+36\red{198}=\blue{54}\times\purple{3}+\pink{36}
    54=36×1+18\red{54}=\blue{36}\times\purple{1}+\pink{18}
    36=18×2+0\red{36}=\blue{18}\times\purple{2}+\pink{0}
    Puis on remplit le tableau ligne par ligne :
    L2=L0−1×L1\text{L}_{2}=\text{L}_{0}-\purple{1}\times\text{L}_{1} : r=252−198=54r=252-198=54 ; u=1−0=1u=1-0=1 ; v=0−1=−1v=0-1=-1
    L3=L1−3×L2\text{L}_{3}=\text{L}_{1}-\purple{3}\times\text{L}_{2} : r=198−3×54=36r=198-3\times 54=36 ; u=0−3×1=−3u=0-3\times 1=-3 ; v=1−3×(−1)=4v=1-3\times\left(-1\right)=4
    L4=L2−1×L3\text{L}_{4}=\text{L}_{2}-\purple{1}\times\text{L}_{3} : r=54−36=18r=54-36=18 ; u=1−(−3)=4u=1-\left(-3\right)=4 ; v=−1−4=−5v=-1-4=-5
    L5=L3−2×L4\text{L}_{5}=\text{L}_{3}-\purple{2}\times\text{L}_{4} : r=36−2×18=0r=36-2\times 18=0 : on s'arrête.
    Question 2

    En déduire PGCD(252;198)\text{PGCD}\left(252;198\right) et un couple (u;v)\left(u;v\right) tel que 252u+198v=PGCD(252;198)252u+198v=\text{PGCD}\left(252;198\right). Vérifier.

    Correction
    Le dernier reste non nul est celui de la ligne L4\text{L}_{4} : PGCD(252;198)=18\text{PGCD}\left(252;198\right)=18, avec u=4u=4 et v=−5v=-5.
    Vérification : 252×4+198×(−5)=1  008−990=18252\times 4+198\times\left(-5\right)=1\;008-990=18
    Un couple qui convient est donc :
    (u;v)=(4;−5)\left(u;v\right)=\left(4;-5\right) avec 252×4+198×(−5)=18252\times 4+198\times\left(-5\right)=18
    Question 3

    Utiliser la même méthode pour trouver un couple (u;v)\left(u;v\right) d'entiers relatifs tel que 43u+17v=143u+17v=1.

    Correction
    Algorithme d'Euclide :
    43=17×2+9\red{43}=\blue{17}\times\purple{2}+\pink{9}
    17=9×1+8\red{17}=\blue{9}\times\purple{1}+\pink{8}
    9=8×1+1\red{9}=\blue{8}\times\purple{1}+\pink{1}
    8=1×8+0\red{8}=\blue{1}\times\purple{8}+\pink{0}
    Le dernier reste non nul vaut 11 : 4343 et 1717 sont premiers entre eux. Le tableau donne les coefficients :
    La ligne L4\text{L}_{4} donne u=2u=2 et v=−5v=-5.
    Vérification : 43×2+17×(−5)=86−85=143\times 2+17\times\left(-5\right)=86-85=1
    (u;v)=(2;−5)\left(u;v\right)=\left(2;-5\right)

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.