{"id":234124,"date":"2022-07-04T17:19:54","date_gmt":"2022-07-04T15:19:54","guid":{"rendered":"https:\/\/sherpas.com\/blog\/?p=234124"},"modified":"2025-09-29T11:29:54","modified_gmt":"2025-09-29T09:29:54","slug":"comment-calculer-le-pgcd-avec-l-algorithme-d-euclide","status":"publish","type":"post","link":"https:\/\/sherpas.com\/blog\/comment-calculer-le-pgcd-avec-l-algorithme-d-euclide\/","title":{"rendered":"Comment calculer le PGCD avec l\u2019algorithme d\u2019Euclide ?"},"content":{"rendered":"\n

Tu ne sais pas comment calculer le PGCD<\/strong> de deux nombres facilement ? Euclide, un grand math\u00e9maticien de la Gr\u00e8ce Antique, a trouv\u00e9 une m\u00e9thode imparable. Dans ce cours, apprends \u00e0 calculer le PGCD avec l’algorithme d’Euclide<\/strong>. <\/p>\n\n\n\n

Et pour r\u00e9soudre le casse-t\u00eate du PGCD comme un pro, inscris-toi \u00e0 des cours de maths en ligne personnalis\u00e9s<\/a><\/strong> o\u00f9 tu pourras explorer en profondeur l\u2019antique m\u00e9thode d\u2019Euclide. \ud83e\udde9<\/p>\n\n\n\n

Th\u00e9or\u00e8me : Th\u00e9or\u00e8me d’Euclide<\/strong><\/p>\n\n\n\n\nSoient deux entiers relatifs \"a\" et \"b\". On suppose \"b \in\mathbb{N}^*\". On note \"q\" et \"r\" le quotient et le reste de la division de \"a\" par \"b\". Alors :\n

  <\/span>   <\/span>\"\[<\/p>\n\n\n\n

D\u00e9monstration :<\/strong><\/p>\n\n\n\n\nPar d\u00e9finition de \"r\" et \"b\", on a : \"a = bq+r\". On note \"\mathscr{A}\" l’ensemble des diviseurs communs de \"a\" et \"b\" et \"\mathscr{R}\" l’ensemble des diviseurs communs de \"r\" et \"b\". Montrons que \"\mathscr{A} = \mathscr{R}\" par double inclusion.\n\n\n\n

<\/div>\n\n\n\n\nSoit \"d \in\mathscr{R}\", comme \"a = bq + r\" et que \"d\" divise \"r\" et \"b\", on en d\u00e9duit que \"d\" divise aussi \"a\" et donc \"d \in\mathscr{A}\", d’o\u00f9 l’inclusion \"\mathscr{R} \subset \mathscr{A}\".\n\n\n\n
<\/div>\n\n\n\n\nSoit \"d \in\mathscr{A}\", comme \"r = a-bq\" et que \"d\" divise \"a\" et \"b\", on en d\u00e9duit que \"d\" divise aussi \"r\" et donc \"d \in\mathscr{R}\", d’o\u00f9 l’inclusion \"\mathscr{A} \subset \mathscr{R}\".\n\n\n\n
<\/div>\n\n\n\n\nEn conclusion, \"\mathscr{A} = \mathscr{R}\"\n\n\n\n
<\/div>\n\n\n\n\nCes deux ensembles ont donc le m\u00eame plus grand \u00e9l\u00e9ment, soit : \"a \wedge b = b \wedge r\".\n\n\n\n
<\/div>\n\n\n\n

Corollaire : L’algorithme d’Euclide<\/strong><\/p>\n\n\n\n\nVoici un algorithme qui permet de d\u00e9terminer le PGCD de deux entiers non nuls \"a\" et \"b\". Pour cela, on d\u00e9finit une suite \"(r_n)_{n\in\mathbb{N}}\" :\n

  • On pose \"r_0 = a\" et \"r_1 = b\" ; <\/li>\n
  • Tant que \"r_k \ne 0\", on effectue la division euclidienne<\/a> de \"r_{k-1}\" par \"r_k\" et on note \"r_{k+1}\" le nouveau reste obtenu.<\/li>\n\n\n\n
    <\/div>\n\n\n\n\nLe PGCD de \"a\" et \"b\" est le dernier terme de la suite \"(r_n)_{n\in\mathbb{N}}\" non nul.\n\n\n\n

    Remarque : <\/strong><\/p>\n\n\n\n\nSi on note \"n\" le premier entier naturel tel que \"r_n = 0\", le th\u00e9or\u00e8me d’Euclide nous permet d’\u00e9crire que : \n

      <\/span>   <\/span>\"\[<\/p>\nOr, \"r_{n-1} \wedge r_n = r_{n-1} \wedge 0 = r_{n-1}\".\n\n\n\n

    <\/div>\n\n\n\n

    Exemple : <\/strong><\/p>\n\n\n\n

    D\u00e9terminons le PGCD de 2020 et 150 en utilisant l’algorithme d’Euclide : <\/p>\n\n\n\n

    \n
    \n\n\"r_0\" = 2020\n
    2020 = 150 \"\times\" 13 + 70,\n
    150 = 70 \"\times\" 2 + 10,\n
    70 = 10 \"\times\" 7 + 0\n<\/div>\n\n\n\n
    \n\net \"r_1\" = 150\n
    donc \"r_2\" = 70\n
    donc \"r_3\" = 10\n
    donc \"r_4\" = 0\n<\/div>\n<\/div>\n\n\n\n\nLe dernier reste non nul est \"r_3\", donc 2020 \"\wedge\" 150 = 10\n\n\n\n
    \n
    \n
    \"livre<\/figure>\n<\/div>\n\n\n\n
    <\/div>\n\n\n\n
    \n
    <\/div>\n\n\n\n

    Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, m\u00e9thodes, entra\u00eenement et corrig\u00e9s <\/em>(\u00e9ditions Vuibert, juin 2021) <\/em>\u00e9crit par E. Thomas, S. Bellec, G. Boutard. ISBN n\u00b09782311408720<\/em><\/p>\n<\/div>\n<\/div>\n\n\n\n

    <\/p>\n\n\n

    \n \n
    \n \n
    \n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n <\/div>\n \n
    \n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n <\/div>\n<\/div>\n \n\n
    \n 3.7\/5 - (3 votes) <\/div>\n <\/div>\n","protected":false},"excerpt":{"rendered":"

    Tu ne sais pas comment calculer le PGCD de deux nombres facilement ? Euclide, un grand math\u00e9maticien de (…)<\/p>\n","protected":false},"author":158,"featured_media":244625,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":true,"footnotes":""},"category":[803,810],"tag":[78,345],"class_list":["post-234124","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-apprendre-matiere","category-maths","tag-prepa","tag-prepa-scientifique"],"acf":[],"_links":{"self":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/234124","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/users\/158"}],"replies":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/comments?post=234124"}],"version-history":[{"count":0,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/234124\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media\/244625"}],"wp:attachment":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media?parent=234124"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/category?post=234124"},{"taxonomy":"tag","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/tag?post=234124"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}